518. 零钱兑换 II（中）

• 题目
• 法一、回溯
• 法二、动态规划

题目

• 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
  请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
  假设每一种面额的硬币有无限个。
  题目数据保证结果符合 32 位带符号整数。

示例 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 backtrack(coins: List[int],amount: int, track: List[int], res: List[List[int]]):
            #如果减剩的最后结果为0，则将路径加入结果集
            if amount==0:
                res.append(track[:])
                return 
            if amount < 0:
                return
            for i in range(len(coins)):
                track.append(coins[i])#做选择
                backtrack(coins[i:], amount - coins[i],track,res)#递归调用，更新目标值为减去当前候选数后的值，并传递更新后的路径和结果集
                #[i:]避免了重复的组合结果
                track.pop()#撤销选择

        res=[]#结果列表
        track=[]#选择列表
        backtrack(coins,amount,track,res)
        return len(res)

• 超时

法二、动态规划

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)  # 动态规划数组：用于保存凑出每个金额所需的组合数量。
        dp[0] = 1  # base case 表示暂时还没有找到任何组合方式

        for coin in coins:#遍历硬币列表
            for i in range(coin, amount + 1):#对于每个硬币面额 coin，从 coin 开始到目标金额 amount，依次累加动态规划数组中对应位置的值。这样，每个位置 i 的值表示凑出金额 i 的组合数量。
                dp[i] += dp[i - coin]

        return dp[amount]