Coin Change 2

Question (LC.518)

Given a list of coin denominations and a desired amount, find the number of combinations that make up that amount.

Examples

I: amount = 5, coins = [1,2,5]
O: 4 because [1,1,1,1,1], [1,1,1,2],[1,2,2],[5]

I: amount = 3, coins = [2]
O: 0 

I: amount = 10, coins = [10]
O: 1

Approach

# define by prefix 
# dp[i][a] = the number of combinations from coins[:i] to make up amount a 

# solve by prefix 
# choose to use the current coin (new combination) 
# not choose to use the current coin (existing combinations)
# for a from 0 to amount 
#     dp[i][a] = dp[i][a-coins[i]] + dp[i-1][a]

# base case 
# dp[0][0] = 1 (empty set to amount 0 has 1 combination) 

# topo order 
# for i from 0 to n 

# final answer 
# dp[n][amount]

Code

def change(self, amount: int, coins: List[int]) -> int:
    n = len(coins)
    dp: List[List[int]] = [ [0] * (amount + 1) for _ in range(n + 1)] 
    
    # init 
    dp[0][0] = 1
    
    # topo order 
    for i in range(1, n + 1):
        coin_i = i - 1
        # solve by prefix 
        for a in range(amount + 1):
            dp[i][a] += dp[i-1][a]
            if a - coins[coin_i] >= 0:
                dp[i][a] += dp[i][a-coins[coin_i]]

    return dp[n][amount]

Time Complexity

time O(na) space O(na) but can be optimized to O(a)