14.5.2   零钱兑换问题

背包问题是一大类动态规划问题的代表，其拥有很多变种，例如零钱兑换问题。

Question

给定 n 种硬币，第 i 种硬币的面值为 coins[i−1] ，目标金额为 amt ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回 −1 。示例如图 14-24 所示。

图 14-24   零钱兑换问题的示例数据

1.   动态规划思路¶

零钱兑换可以看作完全背包问题的一种特殊情况，两者具有以下联系与不同点。

• 两道题可以相互转换，“物品”对应“硬币”、“物品重量”对应“硬币面值”、“背包容量”对应“目标金额”。
• 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量。
• 完全背包问题是求“不超过”背包容量下的解，零钱兑换是求“恰好”凑到目标金额的解。

第一步：思考每轮的决策，定义状态，从而得到 dp 表

状态 [i,a] 对应的子问题为：前 i 种硬币能够凑出金额 a 的最少硬币数量，记为 dp[i,a] 。

二维 dp 表的尺寸为 (n+1)×(amt+1) 。

第二步：找出最优子结构，进而推导出状态转移方程

本题与完全背包问题的状态转移方程存在以下两点差异。

• 本题要求最小值，因此需将运算符 max() 更改为 min() 。
• 优化主体是硬币数量而非商品价值，因此在选中硬币时执行 +1 即可。

dp[i,a]=min(dp[i−1,a],dp[i,a−coins[i−1]]+1)

第三步：确定边界条件和状态转移顺序

当目标金额为 0 时，凑出它的最少硬币数量为 0 ，即首列所有 dp[i,0] 都等于 0 。

当无硬币时，无法凑出任意 >0 的目标金额，即是无效解。为使状态转移方程中的 min() 函数能够识别并过滤无效解，我们考虑使用 +∞ 来表示它们，即令首行所有 dp[0,a] 都等于 +∞ 。

2.   代码实现¶

大多数编程语言并未提供 +∞ 变量，只能使用整型 int 的最大值来代替。而这又会导致大数越界：状态转移方程中的 +1 操作可能发生溢出。

为此，我们采用数字 amt+1 来表示无效解，因为凑出 amt 的硬币数量最多为 amt 。最后返回前，判断 dp[n,amt] 是否等于 amt+1 ，若是则返回 −1 ，代表无法凑出目标金额。代码如下所示：

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

coin_change.java

[](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-1)/* 零钱兑换：动态规划 */ [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-2)int coinChangeDP(int[] coins, int amt) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-3) int n = coins.length; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-4) int MAX = amt + 1; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-5) // 初始化 dp 表 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-6) int[][] dp = new int[n + 1][amt + 1]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-7) // 状态转移：首行首列 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-8) for (int a = 1; a <= amt; a++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-9) dp[0][a] = MAX; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-10) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-11) // 状态转移：其余行和列 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-12) for (int i = 1; i <= n; i++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-13) for (int a = 1; a <= amt; a++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-14) if (coins[i - 1] > a) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-15) // 若超过目标金额，则不选硬币 i [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-16) dp[i][a] = dp[i - 1][a]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-17) } else { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-18) // 不选和选硬币 i 这两种方案的较小值 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-19) dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1); [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-20) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-21) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-22) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-23) return dp[n][amt] != MAX ? dp[n][amt] : -1; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-30-24)}

可视化运行

图 14-25 展示了零钱兑换的动态规划过程，和完全背包问题非常相似。

<1><2><3><4><5><6><7><8><9><10><11><12><13><14><15>

图 14-25   零钱兑换问题的动态规划过程

3.   空间优化¶

零钱兑换的空间优化的处理方式和完全背包问题一致：

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

coin_change.java

[](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-1)/* 零钱兑换：空间优化后的动态规划 */ [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-2)int coinChangeDPComp(int[] coins, int amt) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-3) int n = coins.length; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-4) int MAX = amt + 1; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-5) // 初始化 dp 表 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-6) int[] dp = new int[amt + 1]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-7) Arrays.fill(dp, MAX); [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-8) dp[0] = 0; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-9) // 状态转移 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-10) for (int i = 1; i <= n; i++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-11) for (int a = 1; a <= amt; a++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-12) if (coins[i - 1] > a) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-13) // 若超过目标金额，则不选硬币 i [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-14) dp[a] = dp[a]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-15) } else { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-16) // 不选和选硬币 i 这两种方案的较小值 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-17) dp[a] = Math.min(dp[a], dp[a - coins[i - 1]] + 1); [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-18) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-19) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-20) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-21) return dp[amt] != MAX ? dp[amt] : -1; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-44-22)}

可视化运行

14.5.3   零钱兑换问题 II¶

Question

给定 n 种硬币，第 i 种硬币的面值为 coins[i−1] ，目标金额为 amt ，每种硬币可以重复选取，问凑出目标金额的硬币组合数量。示例如图 14-26 所示。

图 14-26   零钱兑换问题 II 的示例数据

1.   动态规划思路¶

相比于上一题，本题目标是求组合数量，因此子问题变为：前 i 种硬币能够凑出金额 a 的组合数量。而 dp 表仍然是尺寸为 (n+1)×(amt+1) 的二维矩阵。

当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为：

dp[i,a]=dp[i−1,a]+dp[i,a−coins[i−1]]

当目标金额为 0 时，无须选择任何硬币即可凑出目标金额，因此应将首列所有 dp[i,0] 都初始化为 1 。当无硬币时，无法凑出任何 >0 的目标金额，因此首行所有 dp[0,a] 都等于 0 。

2.   代码实现¶

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

coin_change_ii.java

[](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-1)/* 零钱兑换 II：动态规划 */ [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-2)int coinChangeIIDP(int[] coins, int amt) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-3) int n = coins.length; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-4) // 初始化 dp 表 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-5) int[][] dp = new int[n + 1][amt + 1]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-6) // 初始化首列 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-7) for (int i = 0; i <= n; i++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-8) dp[i][0] = 1; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-9) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-10) // 状态转移 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-11) for (int i = 1; i <= n; i++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-12) for (int a = 1; a <= amt; a++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-13) if (coins[i - 1] > a) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-14) // 若超过目标金额，则不选硬币 i [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-15) dp[i][a] = dp[i - 1][a]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-16) } else { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-17) // 不选和选硬币 i 这两种方案之和 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-18) dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-19) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-20) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-21) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-22) return dp[n][amt]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-58-23)}

可视化运行

3.   空间优化¶

空间优化处理方式相同，删除硬币维度即可：

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

coin_change_ii.java

[](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-1)/* 零钱兑换 II：空间优化后的动态规划 */ [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-2)int coinChangeIIDPComp(int[] coins, int amt) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-3) int n = coins.length; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-4) // 初始化 dp 表 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-5) int[] dp = new int[amt + 1]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-6) dp[0] = 1; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-7) // 状态转移 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-8) for (int i = 1; i <= n; i++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-9) for (int a = 1; a <= amt; a++) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-10) if (coins[i - 1] > a) { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-11) // 若超过目标金额，则不选硬币 i [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-12) dp[a] = dp[a]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-13) } else { [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-14) // 不选和选硬币 i 这两种方案之和 [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-15) dp[a] = dp[a] + dp[a - coins[i - 1]]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-16) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-17) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-18) } [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-19) return dp[amt]; [](https://www.hello-algo.com/chapter_dynamic_programming/unbounded_knapsack_problem/#__codelineno-72-20)}