Medium Unbounded Knapsack 2-D Dynamic Programming
In plain English: Count how many different ways you can make change for a given amount using unlimited coins of each denomination.
Unbounded knapsack variant. dp[j] = number of ways to make amount j. Process coins in outer loop to avoid counting permutations (order doesn't matter). For each coin, dp[j] += dp[j - coin].
Prompt
Given an amount and a list of coin denominations, return the number of combinations that make up that amount. You may use each coin an unlimited number of times.
Try to write it from scratch before scrolling down.
Solution
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make 0: use nothing
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[amount]
# Test: change(5, [1,2,5]) == 4 ({5}, {2+2+1}, {2+1+1+1}, {1*5})
# Test: change(3, [2]) == 0