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

Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів

Все було зрозуміло?

Секція 3. Розділ 4

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

Все було зрозуміло?

Секція 3. Розділ 4

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

Все було зрозуміло?

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

Секція 3. Розділ 4