518零钱兑换

<think>好的，我现在需要回答用户关于零钱兑换 II（力扣 518）的问题，特别是使用动态规划的算法。首先，我需要回顾一下动态规划的基本思路以及这个问题和零钱兑换 I（力扣 322）的区别。零钱兑换 I 是求凑成总金额所需的最少硬币数，而零钱兑换 II 是求凑成总金额的组合数，也就是不同的硬币组合方式的数量。 根据引用中的信息，特别是引用[3]，用户提到了示例输入 amount=5，coins=[1,2,5]，输出4。这说明问题需要计算所有可能的组合数，而不是排列数。例如，2+2+1和2+1+2被认为是同一种组合，因此需要考虑的是硬币的顺序不影响结果。 接下来，动态规划的状态定义是关键。通常，这类问题中，状态dp[i]表示金额i的组合数。但为了确保硬币的顺序不影响结果，需要避免重复计数。引用[2]提到要从小到大遍历金额数，并且在计算dp[i]时，确保前面的金额已经处理过。这可能涉及到外层循环是硬币，内层循环是金额，从而保证每次添加的硬币不会重复之前的排列。 然后，状态转移方程应该是dp[i] += dp[i - coin]，其中coin是当前遍历的硬币面值。这里的逻辑是，对于每个硬币，如果当前金额i大于等于硬币面值，那么i的组合数可以加上i - coin的组合数，因为加上这个硬币就能得到i的组合。同时，由于硬币是按顺序遍历的，这样避免了不同的排列被重复计算。 我需要验证这个思路是否正确。例如，对于示例中的情况，当coins=[1,2,5]，初始化dp[0]=1，然后依次处理每个硬币。处理硬币1时，所有金额都可以由1组成，所以每个金额i对应的组合数都是1种。接着处理硬币2，金额从2开始，dp[2] += dp[0]（即1），所以dp[2]=2（1+1和2）。继续处理更大的金额，直到处理硬币5。这样最终得到dp[5]=4，符合示例的结果。 另外，需要处理初始化和边界条件。dp数组的大小应为amount+1，初始时dp[0]=1，其他为0。遍历的顺序是先硬币后金额，这样可以保证组合不考虑顺序。如果反过来，先金额后硬币，可能会出现排列的情况，导致结果错误。 还要注意测试用例的情况，比如amount为0时应该返回1，因为没有硬币的情况下有一种方式凑成0元。此外，硬币可能有重复或无法凑成的情况，但题目中可能假设硬币数量无限且至少有一个解，但需要确认问题是否有这样的限制。 最后，代码实现需要按照这个逻辑编写，通常使用嵌套循环，外层是硬币，内层是金额从coin到amount。每次更新dp[j] += dp[j - coin]。这样就能正确计算出组合数。</think>### 零钱兑换 II（力扣 518）的动态规划解法 #### 问题描述 给定不同面额的硬币数组 $coins$ 和总金额 $amount$，计算可以凑成总金额的硬币组合数。假设每种面额的硬币数量无限，且组合不考虑顺序。例如，$coins = [1,2,5], amount = 5$ 时，输出为 $4$[^3]。 --- #### 核心思路 1. **状态定义** 定义 $dp[i]$ 表示凑成金额 $i$ 的组合数。初始化时，$dp[0] = 1$（凑出金额 $0$ 的组合数为 $1$，即不选任何硬币），其余初始化为 $0$。 2. **状态转移方程** 对于每枚硬币 $coin$，遍历金额 $j$ 从 $coin$ 到 $amount$，更新方程： $$dp[j] += dp[j - coin]$$ 表示当前金额 $j$ 的组合数等于**已计算的部分**加上使用当前硬币后的组合数[^2]。 3. **遍历顺序** 外层遍历硬币，内层遍历金额。确保组合不考虑顺序（例如，$2+1$ 和 $1+2$ 视为同一种组合）[^3]。 --- #### 算法步骤 1. 初始化 $dp$ 数组：$dp[0] = 1$，其余为 $0$。 2. 遍历每枚硬币 $coin$： - 对于每个金额 $j$ 从 $coin$ 到 $amount$： - 更新 $dp[j] += dp[j - coin]$。 3. 返回 $dp[amount]$。 --- #### 代码实现 ```python def change(amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for j in range(coin, amount + 1): dp[j] += dp[j - coin] return dp[amount] ``` --- #### 示例分析 以 $amount = 5$，$coins = [1,2,5]$ 为例： - **初始化**：$dp = [1,0,0,0,0,0]$ - **处理硬币 $1$**： - 更新所有金额 $j$：$dp[j] += dp[j-1]$，得到 $dp = [1,1,1,1,1,1]$ - **处理硬币 $2$**： - 从 $j=2$ 开始更新： - $dp[2] += dp[0] = 1 + 1 = 2$ - $dp[3] += dp[1] = 1 + 1 = 2$ - $dp[4] += dp[2] = 1 + 2 = 3$ - $dp[5] += dp[3] = 1 + 2 = 3$ - 更新后 $dp = [1,1,2,2,3,3]$ - **处理硬币 $5$**： - 从 $j=5$ 开始更新： - $dp[5] += dp[0] = 3 + 1 = 4$ - 最终结果 $dp[5] = 4$。 --- #### 性能分析 - **时间复杂度**：$O(n \cdot m)$，其中 $n$ 是金额 $amount$，$m$ 是硬币种类数。 - **空间复杂度**：$O(n)$，仅需一维数组存储状态。 ---