518. 零钱兑换 II -- 完全背包

518. 零钱兑换 II

这道题其实就是一个完全背包问题，关于背包问题的相关文章见：

1. 01背包问题 – 动态规划
2. 完全背包问题

class CoinChange:
    """
    完全背包
    518. 零钱兑换 II
    https://leetcode.cn/problems/coin-change-ii/
    """
    def solution(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        #  dp[i][j]: 若只使⽤前 i 个物品（可以重复使⽤），当背包容量为 j 时，有 dp[i][j] 种⽅法可以装满背包。
        dp = [[0 for _ in range(amount+1)] for _ in range(n+1)]

        # base case
        for i in range(n + 1):
            dp[i][0] = 1

        for i in range(1, n+1):
            for j in range(1, amount+1):
                if j - coins[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[n][amount]

    def solution2(self, amount: int, coins: List[int]) -> int:
        """
        空间压缩，二维变一维
        :param amount:
        :param coins:
        :return:
        """
        n = len(coins)
        #  dp[j]: 当背包容量为 j 时，有 dp[j] 种⽅法可以装满背包。
        dp = [0 for _ in range(amount + 1)]

        # base case
        dp[0] = 1

        for i in range(n):
            # 这里只能从前往后正向遍历，因为要考虑重复使用的情况，区别在于这里 dp[i][j-coins[i-1]]
            # 当使用了coins[i]这枚硬币时，可重复多次使用，所以不是 dp[i-1][j-coins[i-1]]
            # dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
            for j in range(1, amount + 1):
                if j - coins[i] >= 0:
                    dp[j] = dp[j] + dp[j - coins[i]]

        return dp[amount]