518 零钱兑换II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

解法

• 递归，超时

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def test(amount,coins,res):
            num = 0
            if res>amount:
                return 0
            if res==amount:
                return 1

            for i in range(len(coins)):
                res += coins[i]
                num += test(amount,coins[i:],res)
                res -= coins[i]
            return num

        coins.sort()
        return test(amount,coins,0)

• 动态规划

状态方程：

dp[i][j]表示前i个coins组合成钱j的组合数。
若 j<coins[i]:
    dp[i][j] = dp[i-1][j]
否则: dp[i][j] = dp[i-1][j]+dp[i-1][j-coins[i]]

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