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
Resumir este capítulo
Explicar el código en file
Explicar por qué file no resuelve la tarea
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
