Kursinhalt
Dynamic Programming
Dynamic Programming
Problem D. Coin Change
Imagine you got N cents as combination of some coins, and the last added coin was C. Then, number of possible combinations dp[N] is equal to dp[N-C]. Consider that you can reach N cents by adding either c[0], c[1], ... ,c[m-1] cents, so number of possible combinations is:
dp[N] = dp[N-c[0]] + dp[N-c[1]] + ... + dp[N-c[m-1]]
Note that value of N-c[i] must be non-negative. Let's use tabulation: for values j from coin up to N: update dp[j] with adding dp[j-coin]; repeat for each coin.
def coinChange(n , coins): dp = [0 for _ in range(n+1)] dp[0] = 1 for i in range(len(coins)): for j in range(coins[i], n+1): dp[j] += dp[j-coins[i]] return dp[n] print(coinChange(14, [1,2,3,7])) print(coinChange(100, [2,3,5,7,11]))
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwendenDanke für Ihr Feedback!
Problem D. Coin Change
Imagine you got N cents as combination of some coins, and the last added coin was C. Then, number of possible combinations dp[N] is equal to dp[N-C]. Consider that you can reach N cents by adding either c[0], c[1], ... ,c[m-1] cents, so number of possible combinations is:
dp[N] = dp[N-c[0]] + dp[N-c[1]] + ... + dp[N-c[m-1]]
Note that value of N-c[i] must be non-negative. Let's use tabulation: for values j from coin up to N: update dp[j] with adding dp[j-coin]; repeat for each coin.
def coinChange(n , coins): dp = [0 for _ in range(n+1)] dp[0] = 1 for i in range(len(coins)): for j in range(coins[i], n+1): dp[j] += dp[j-coins[i]] return dp[n] print(coinChange(14, [1,2,3,7])) print(coinChange(100, [2,3,5,7,11]))
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwendenDanke für Ihr Feedback!
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwenden