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]))
¡Gracias por tus comentarios!
single
Pregunte a AI
Pregunte a AI
Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla
Awesome!
Completion rate improved to 8.33Problem D. Coin Change
Desliza para mostrar el menú
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]))
Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones¡Gracias por tus comentarios!
Awesome!
Completion rate improved to 8.33single
