518. Coin Change II

https://leetcode.com/problems/coin-change-ii/

solution

• 完全背包

  • 01背包和完全背包区别在于，对背包遍历顺序是右到左，还是左到右

  • 注意遍历顺序，物品还是背包决定了结果是排列还是组合

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

时间复杂度：O(|coins|⋅amount) 空间复杂度：O(amount)