7.6 贪心何时失败
这一节回答什么问题？
什么时候不该用贪心？
贪心失败的三种情况
- 缺乏最优子结构：最长简单路径——最优解的子路径不一定最优
- 贪心选择性质不成立：0-1背包——最优解可能不含贪心选择
- 子问题重叠：需要 DP 记忆化
LLM时代映射
LLM 的贪心解码 = 每步选最高概率 token。
这正是贪心算法的同一陷阱：局部最优不保证全局最优。
贪心解码可能：
- 陷入重复模式
- 不探索替代路径
- 错过更好的表达方式
本节小结
这一节解决了什么问题？
贪心什么时候不该用？
核心洞察是什么？
贪心失败的三种原因：无最优子结构、无贪心选择性质、子问题重叠。
如何判断？
检查问题结构——是否存在这三类障碍。
LLM启示
理解贪心何时有效，就是理解何时可以信任 LLM 的单步最优选择。