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.
12345678910def 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]))
Merci pour vos commentaires !
single
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Résumer ce chapitre
Expliquer le code dans file
Expliquer pourquoi file ne résout pas la tâche
Génial!
Completion taux amélioré à 8.33Problem D. Coin Change
Glissez pour afficher le menu
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.
12345678910def 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]))
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
single
