2019-05-31LeetCode518. 零钱兑换 II

Please note that the outer loop should be about coins, while the inner loop should be about amount. Or else, there may be duplicates in the result, e.g. for input: amount = 5, coins = [1, 2, 5], it counts [2, 2, 1] and [2, 1, 2] as two different combinations, so it will return 9 rather than 5. All in all, the order of coins doesn't matterin this case, so we set it as the outer loop.
背包问题

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