Veeg om het menu te tonen

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

Schakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 4

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Problem D. Coin Change

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

Schakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 4

Schakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties