知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 零钱兑换 ## 题目(LeetCode 322) 给定不同面额的硬币和总金额 amount,求凑成总金额所需的最少硬币数。每种硬币无限使用。 ``` 输入:coins=[1,2,5], amount=11 输出:3(5+5+1) ``` ## 先搞清楚:完全背包 vs 0-1 背包 ``` 0-1 背包:每个物品只能用一次 → 选了就没了 完全背包:每个物品可以用无限次 → 零钱兑换就是完全背包,每种硬币可以无限用 区别只在代码的一个细节:内层循环的方向(后面会讲) ``` ## 大白话理解 凑 11 元,有 1 元、2 元、5 元硬币,最少用几枚? 想象你在自动贩卖机前投币,每次投一枚,问最少投几次能凑够。 核心思路:凑出金额 i 的最后一步,一定是放了某枚硬币 coin,那之前需要凑出 i-coin。 ``` 凑 11 元的最后一步: 放了 1 元 → 之前凑了 10 元,dp[11] = dp[10] + 1 放了 2 元 → 之前凑了 9 元,dp[11] = dp[9] + 1 放了 5 元 → 之前凑了 6 元,dp[11] = dp[6] + 1 取三种情况的最小值 ``` ## 四步法 ``` 第 1 步:dp[i] = 凑出金额 i 所需的最少硬币数 第 2 步:dp[i] = min(dp[i - coin] + 1) 对所有 coin 对每种硬币,如果 coin <= i,就可以用这枚硬币 用了这枚硬币后,还需要凑 i-coin,需要 dp[i-coin] 枚 加上这枚硬币本身,共 dp[i-coin]+1 枚 取所有硬币中的最小值 第 3 步:dp[0] = 0(凑 0 元不需要任何硬币) dp[1..amount] = amount+1(初始化为不可能的大值,相当于正无穷) 第 4 步:从小到大遍历(凑 i 元依赖凑 i-coin 元,i-coin < i,所以先算小的) ``` ### 为什么初始化为 amount+1 而不是 Integer.MAX_VALUE? ``` 如果用 Integer.MAX_VALUE,那 dp[i-coin] + 1 会整数溢出! amount+1 是一个"不可能达到的值"(最多用 amount 枚 1 元硬币), 所以用它代表"无法凑出",安全又方便。 ``` ## 手动模拟(这是理解的关键) ``` coins=[1,2,5], amount=11 初始化:dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] 0 1 2 3 4 5 6 7 8 9 10 11 dp[0] = 0(凑 0 元,0 枚) dp[1]: 用 1 元:dp[1-1]+1 = dp[0]+1 = 1 用 2 元:2 > 1,跳过 用 5 元:5 > 1,跳过 dp[1] = 1 dp[2]: 用 1 元:dp[2-1]+1 = dp[1]+1 = 2 用 2 元:dp[2-2]+1 = dp[0]+1 = 1 ← 更小 用 5 元:5 > 2,跳过 dp[2] = 1 dp[3]: 用 1 元:dp[2]+1 = 2 用 2 元:dp[1]+1 = 2 用 5 元:5 > 3,跳过 dp[3] = 2(1+2 或 2+1) dp[4]: 用 1 元:dp[3]+1 = 3 用 2 元:dp[2]+1 = 2 ← 更小 用 5 元:5 > 4,跳过 dp[4] = 2(2+2) dp[5]: 用 1 元:dp[4]+1 = 3 用 2 元:dp[3]+1 = 3 用 5 元:dp[0]+1 = 1 ← 最小 dp[5] = 1(直接用 5 元) dp[6]: 用 1 元:dp[5]+1 = 2 用 2 元:dp[4]+1 = 3 用 5 元:dp[1]+1 = 2 dp[6] = 2(5+1) dp[7]: 用 1 元:dp[6]+1 = 3 用 2 元:dp[5]+1 = 2 ← 更小 用 5 元:dp[2]+1 = 2 ← 一样小 dp[7] = 2(5+2) dp[8]: 用 1 元:dp[7]+1 = 3 用 2 元:dp[6]+1 = 3 用 5 元:dp[3]+1 = 3 dp[8] = 3(5+2+1 或 5+1+2 等) dp[9]: 用 1 元:dp[8]+1 = 4 用 2 元:dp[7]+1 = 3 用 5 元:dp[4]+1 = 3 dp[9] = 3(5+2+2) dp[10]: 用 1 元:dp[9]+1 = 4 用 2 元:dp[8]+1 = 4 用 5 元:dp[5]+1 = 2 ← 最小 dp[10] = 2(5+5) dp[11]: 用 1 元:dp[10]+1 = 3 用 2 元:dp[9]+1 = 4 用 5 元:dp[6]+1 = 3 dp[11] = 3(5+5+1)✓ 最终 dp 数组: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3] 0 1 2 3 4 5 6 7 8 9 10 11 ``` ## 代码 ```java public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); // 初始化为不可能的大值 dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } ``` ## 变体:零钱兑换 II(LeetCode 518)— 求组合数 ### 题目 ``` 输入:coins=[1,2,5], amount=5 输出:4(有 4 种组合:5, 2+2+1, 2+1+1+1, 1+1+1+1+1) ``` ### 和零钱兑换 I 的区别 ``` 零钱兑换 I:求最少硬币数(最优化问题) 零钱兑换 II:求组合数(计数问题) dp[i] 的含义变了: I:dp[i] = 凑出 i 的最少硬币数 II:dp[i] = 凑出 i 的组合数 ``` ### 关键:循环顺序不同! ``` 零钱兑换 I(最少硬币数): 外层遍历金额,内层遍历硬币 for i in 1..amount: for coin in coins: dp[i] = min(dp[i], dp[i-coin]+1) 零钱兑换 II(组合数): 外层遍历硬币,内层遍历金额 for coin in coins: for i in coin..amount: dp[i] += dp[i-coin] 为什么顺序不同? 组合数问题要避免重复计数: [1,2] 和 [2,1] 是同一种组合,不能算两次 外层遍历硬币:保证每种硬币按顺序考虑 → 先考虑 1 元,再考虑 2 元 → 不会出现 [2,1] 这种顺序(因为 2 元在 1 元之后才考虑) → 自然去重 ``` ### 手动模拟(coins=[1,2,5], amount=5) ``` dp = [1, 0, 0, 0, 0, 0] 初始化 dp[0]=1(凑 0 元有 1 种方法:什么都不选) 处理 coin=1: i=1: dp[1] += dp[0] = 1 → dp=[1,1,0,0,0,0] i=2: dp[2] += dp[1] = 1 → dp=[1,1,1,0,0,0] i=3: dp[3] += dp[2] = 1 → dp=[1,1,1,1,0,0] i=4: dp[4] += dp[3] = 1 → dp=[1,1,1,1,1,0] i=5: dp[5] += dp[4] = 1 → dp=[1,1,1,1,1,1] 此时只用 1 元硬币,每种金额只有 1 种方法 处理 coin=2: i=2: dp[2] += dp[0] = 1+1 = 2 → dp=[1,1,2,1,1,1] i=3: dp[3] += dp[1] = 1+1 = 2 → dp=[1,1,2,2,1,1] i=4: dp[4] += dp[2] = 1+2 = 3 → dp=[1,1,2,2,3,1] i=5: dp[5] += dp[3] = 1+2 = 3 → dp=[1,1,2,2,3,3] 加入 2 元硬币后,凑 5 元有 3 种:1+1+1+1+1, 2+1+1+1, 2+2+1 处理 coin=5: i=5: dp[5] += dp[0] = 3+1 = 4 → dp=[1,1,2,2,3,4] 加入 5 元硬币后,凑 5 元有 4 种:1+1+1+1+1, 2+1+1+1, 2+2+1, 5 答案 = dp[5] = 4 ✓ ``` ### 代码 ```java public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { // 外层遍历硬币 for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; } ``` ## 注意:容易困惑的地方 ``` Q:为什么零钱兑换 I 外层遍历金额,II 外层遍历硬币? A: I 是最优化问题,两种顺序都能得到正确答案(因为取 min,不会重复计数) II 是计数问题,必须外层遍历硬币,否则 [1,2] 和 [2,1] 会被算两次 Q:dp[0] = 1 是什么意思? A:凑出 0 元有 1 种方法:什么都不选。 这是计数问题的标准初始化,类似于"空集是任何集合的子集"。 Q:如果凑不出来怎么办? A:dp[amount] 会保持初始值 0(没有任何方法能凑出),返回 0。 零钱兑换 I 中,dp[amount] > amount 说明凑不出,返回 -1。 ``` ## 一句话总结 完全背包:`dp[i] = min(dp[i-coin]+1)`,外层金额内层硬币。求组合数时外层硬币内层金额,避免重复计数。 --- 上一篇:[04 - 最长递增子序列](./04-lis.md) | 下一篇:[06 - 最长公共子序列](./06-lcs.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入