518. 零钱兑换 II -- 完全背包-Toy模板网

这篇具有很好参考价值的文章主要介绍了518. 零钱兑换 II -- 完全背包。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

518. 零钱兑换 II

这道题其实就是一个完全背包问题，关于背包问题的相关文章见：文章来源地址https://www.toymoban.com/news/detail-709298.html

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


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]