518. Coin Change II

link

Unbounded Knapsack

Backtrack

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:

        n = len(coins)

        # add this large increase speed
        coins.sort(reverse=True)

        @cache
        def backtrack(current, i):
            if current > amount:
                return 0
            if current == amount:
                return 1

            res = 0

            for j in range(i, n):
                res += backtrack(current + coins[j], j)

            return res

        return backtrack(0, 0)

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        @cache
        def backtrack(a, i):
            if a == amount:
                return 1
            if a > amount:
                return 0
            if i == len(coins):
                return 0
        
            # get or not get
            return backtrack(a + coins[i], i) + backtrack(a, i + 1)

        return backtrack(0, 0)

DP

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

# reduce space complexity
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)

        coins.sort()

        dp = [0] * (amount + 1)
        dp[0] = 1

        for c in coins:
            for i in range(amount+1):
                if i - c >= 0:
                    dp[i] += dp[i - c]

        return dp[-1]