518. Coin Change 2 - cocoder39/coco39_LC GitHub Wiki

518. Coin Change 2

unbounded Knapsack problem

Caveat:

1. iterating coins then amount.
   • Attempted to iterate amount then coin, which causes duplication (eg, 3 = 1 + 2 = 2 + 1, but the combination of 1 and 2 should be counted as 1)
   • instead, try to build amount purely with coins[i], then coins[i+1].. to avoid duplication
2. dp[i-1][j-coins[i-1]] doesn't need to be covered. dp[i][j] means max ways to gaining j via using coins[:i+1]. That said, dp[i-1][j-coins[i-1]] is covered by dp[i][j-coins[i-1]]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        
        dp = [[0] * (amount+1) for i in range(n+1)]
        
        for i in range(n+1):
            dp[i][0] = 1
            
        for i in range(1, n+1):
            for j in range(1, amount+1):
                dp[i][j] = dp[i-1][j] + (dp[i][j-coins[i-1]] if j >= coins[i-1] else 0)
        return dp[n][-1]

compacting space

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:        
        dp = [0] * (amount+1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] += dp[i-coin]
        return dp[-1]