专题进阶 · 贪心策略推荐总顺序 · 第 84 / 148 课

用最小反例区分贪心选择和最优子结构,解释何时必须保留多个状态。

先学会这些,再进入本课 贪心思想 一维 DP 完全背包
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 贪心策略

DP 与贪心DP vs Greedy

DP 保留多个状态比较未来代价,贪心需要证明当前选择不会损失最优解。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用最小反例区分贪心选择和最优子结构,解释何时必须保留多个状态。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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)=24+1
dp[6]min(3,2,3)=23+3

窄屏可左右滑动表格,阅读完整计算与理由。

DP 的状态数更多,但没有未经证明地丢弃未来可能更好的方案。

04为什么这个方法成立

  1. 任一凑法都有最后一枚硬币 c。
  2. 去掉它得到金额 x−c 的凑法,用更少枚数的最优凑法替换不会变差。
  3. 遍历所有 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

面值 [2],金额 3 返回什么?

需要一点提示

无法恰好组成。

查看解析与答案

−1,不应返回 0 或向上取整后的 2。

练习 2 · 边界与辨析

面值 [1,2,4],金额 6 贪心会错吗?

需要一点提示

二次幂结构。

查看解析与答案

本例得到 4+2 两枚,正确;但单个成功样本不构成该币制的完整证明。

练习 3 · 变式与迁移

怎样证明一个新的贪心规则?

需要一点提示

找能替换任意最优解的局部结构。

查看解析与答案

尝试交换论证、割性质或保持可扩展最优解的不变量;若卡住,先枚举小例寻找反例,而非直接宣称正确。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。