Apprendre 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.


              12345678910
            
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]))

Tout était clair ?

Merci pour vos commentaires !

Section 3. Chapitre 4

single

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Suggested prompts:

Résumer ce chapitre

Expliquer le code dans file

Expliquer pourquoi file ne résout pas la tâche

Glissez pour afficher le menu