01先把问题说具体
硬币面值 [1,3,4],凑金额 6。每次取最大可用面值,为什么不总能用最少硬币?
02一步步得到方法
局部更大不代表剩余问题更容易
贪心先取 4,余下 2 只能取 1+1,共三枚;先取 3 再取 3,只需两枚。当前取值大确实让剩余金额更小,但剩余金额的可表示结构也改变了。
这一个合法反例就足以否定通用规则,不需要找很多样本。某些特殊币制可证明贪心正确,但结论不能推广到任意面值。
DP 保留每个金额的最佳结果
定义 dp[x] 为凑成恰好 x 的最少枚数。最后一枚可能是任一 c≤x,因此 dp[x]=min(dp[x−c]+1)。dp[0]=0,其他初始无穷表示尚不可达。
最优子结构只说明固定最后一枚后,剩余部分应最优;它并未说明应该固定哪一枚。DP 比较所有候选,贪心要额外证明某一选择可以安全排除其他候选。
用反例定位缺失的选择性质
硬币面额 [1,3,4]、目标6,最大面额优先得到4+1+1,而最优为3+3。问题仍有最优子结构,但局部取最大硬币并不安全,说明最优子结构不足以支持贪心。
DP 可以比较所有合法最后一步,通过状态保存剩余目标的最优值。若某种特殊输入具备可证明的贪心性质,可以减少这些比较;决定依据是结构证明,不是贪心代码较短。
03把一个小例子完全算清楚
面值 1、3、4,目标 6。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| dp[0..2] | [0,1,2] | 只能使用面值 1 |
| dp[3]、dp[4] | 1、1 | 直接取一枚 |
| dp[5] | min(dp[4]+1,dp[2]+1,dp[1]+1)=2 | 4+1 |
| dp[6] | min(3,2,3)=2 | 3+3 |
窄屏可左右滑动表格,阅读完整计算与理由。
DP 的状态数更多,但没有未经证明地丢弃未来可能更好的方案。
04为什么这个方法成立
- 任一凑法都有最后一枚硬币 c。
- 去掉它得到金额 x−c 的凑法,用更少枚数的最优凑法替换不会变差。
- 遍历所有 c 取最小,所以状态答案最优;不可达状态维持无穷。
05把推导翻译成代码
Python · 可独立运行的教学实现
def minimum_coins(coins, amount):
assert amount >= 0 and all(c > 0 for c in coins)
dp = [0] + [float("inf")]*amount
for x in range(1,amount+1):
for coin in coins:
if coin <= x:
dp[x] = min(dp[x],dp[x-coin]+1)
return -1 if dp[amount] == float("inf") else dp[amount]逐个理解关键决定
[float("inf")]*amount- 恰好金额问题不能用零初始化未知状态。
for coin in coins- 对最后一枚的全部合法候选做比较,而非只选最大币值。
06时间、空间与实现范围
面值数 k、金额 A,时间 O(kA),空间 O(A),属于伪多项式算法。
若存在贪心正确性证明,可能用更低成本直接构造;若没有,不能用速度替代正确性。
07改变条件,检查哪里会出错
问题有最优子结构,所以贪心一定成立
最优子结构也是 DP 的依据,贪心还需要安全局部选择性质。
看到样例通过就放弃 DP
应先找小规模反例或证明局部选择可交换进最优解,再决定能否收窄选择。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
面值 [2],金额 3 返回什么?
需要一点提示
无法恰好组成。
查看解析与答案
−1,不应返回 0 或向上取整后的 2。
面值 [1,2,4],金额 6 贪心会错吗?
需要一点提示
二次幂结构。
查看解析与答案
本例得到 4+2 两枚,正确;但单个成功样本不构成该币制的完整证明。
怎样证明一个新的贪心规则?
需要一点提示
找能替换任意最优解的局部结构。
查看解析与答案
尝试交换论证、割性质或保持可扩展最优解的不变量;若卡住,先枚举小例寻找反例,而非直接宣称正确。