线性动态规划：零钱兑换 II（Coin Change II）

问题描述

给定一个整数数组 coins 表示不同面额的硬币（每种硬币数量无限），以及一个整数 amount 表示总金额。计算可以凑成总金额的硬币组合数（即不同的硬币排列视为相同的组合，例如 [1,2] 和 [2,1] 算作同一种）。如果没有任何硬币组合能组成总金额，则返回 0。

示例：

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

解题思路

这是一个典型的完全背包问题，属于线性动态规划的范畴。我们需要计算组合数，而不是排列数。关键点在于如何设计动态规划状态转移，确保不重复计算排列。

核心步骤分解

1. 状态定义
   定义 dp[i] 为凑成金额 i 的组合数。我们的目标是计算 dp[amount]。

2. 初始化
   dp[0] = 1，表示凑成金额 0 只有一种组合：不选取任何硬币。其他 dp[i] 初始化为 0。

3. 状态转移
   我们需要确保计算的是组合数，而不是排列数。为了实现这一点，我们采用外层循环遍历硬币面额，内层循环遍历金额的方式。这样，对于每个硬币，我们考虑将它加入组合时，只会按照硬币的顺序进行更新，从而避免排列重复。

   转移方程：

   对于每个硬币 coin 在 coins 中：
       对于每个金额 j 从 coin 到 amount：
           dp[j] += dp[j - coin]
   

   解释：当考虑硬币 coin 时，金额 j 的组合数等于不用 coin 的组合数（即之前的 dp[j]）加上用 coin 的组合数（即 dp[j - coin]，表示在金额 j - coin 的组合基础上加上一个 coin）。

4. 最终结果
   dp[amount] 即为所求组合数。

详细讲解步骤

让我们用示例 coins = [1, 2, 5], amount = 5 来逐步演示。

步骤 1：初始化

dp[0] = 1, dp[1] = dp[2] = dp[3] = dp[4] = dp[5] = 0

初始状态表示只有金额 0 有一种组合（空组合）。

步骤 2：遍历硬币面额 1

• 硬币 coin = 1，遍历金额 j 从 1 到 5：
  • j = 1：dp[1] += dp[0] → dp[1] = 0 + 1 = 1（组合：[1]）
  • j = 2：dp[2] += dp[1] → dp[2] = 0 + 1 = 1（组合：[1,1]）
  • j = 3：dp[3] += dp[2] → dp[3] = 0 + 1 = 1（组合：[1,1,1]）
  • j = 4：dp[4] += dp[3] → dp[4] = 0 + 1 = 1（组合：[1,1,1,1]）
  • j = 5：dp[5] += dp[4] → dp[5] = 0 + 1 = 1（组合：[1,1,1,1,1]）

此时 dp = [1, 1, 1, 1, 1, 1]。

步骤 3：遍历硬币面额 2

• 硬币 coin = 2，遍历金额 j 从 2 到 5：
  • j = 2：dp[2] += dp[0] → dp[2] = 1 + 1 = 2（组合：[1,1] 和 [2]）
  • j = 3：dp[3] += dp[1] → dp[3] = 1 + 1 = 2（组合：[1,1,1] 和 [1,2]）
  • j = 4：dp[4] += dp[2] → dp[4] = 1 + 2 = 3（组合：[1,1,1,1]、[1,1,2]、[2,2]）
  • j = 5：dp[5] += dp[3] → dp[5] = 1 + 2 = 3（组合：[1,1,1,1,1]、[1,1,1,2]、[1,2,2]）

此时 dp = [1, 1, 2, 2, 3, 3]。

步骤 4：遍历硬币面额 5

• 硬币 coin = 5，遍历金额 j 从 5 到 5：
  • j = 5：dp[5] += dp[0] → dp[5] = 3 + 1 = 4（新增组合：[5]）

此时 dp = [1, 1, 2, 2, 3, 4]。

步骤 5：最终结果

dp[5] = 4，与示例相符。

为什么外层循环硬币能避免排列重复？

因为这种循环顺序保证了对于任意组合，硬币的选取顺序是固定的（按照 coins 数组中的顺序）。例如，组合 [1,2] 只会在先处理硬币 1、再处理硬币 2 时被计入一次，而不会在处理硬币 2 后再处理硬币 1 时重复计入。这样就确保了计算的是组合数，而不是排列数。

复杂度分析

• 时间复杂度：O(n × amount)，其中 n 是硬币种类数。
• 空间复杂度：O(amount)，只需要一维数组 dp。

关键点总结

1. 状态定义：dp[i] 表示凑成金额 i 的组合数。
2. 初始化：dp[0] = 1，其余为 0。
3. 循环顺序：外层循环硬币，内层循环金额，确保计算的是组合数。
4. 状态转移：dp[j] += dp[j - coin]，表示在组合中加入当前硬币。

拓展思考

如果问题改为计算排列数（即 [1,2] 和 [2,1] 视为不同），则只需交换循环顺序：外层循环金额，内层循环硬币。你可以尝试推导一下，加深对组合与排列区别的理解。