从暴力搜索到更好算法
复习
- 回溯与搜索树：枚举所有可能
- 动态规划：用缓存消除重复子问题
- 贪心选择：每步只选当前最优
TL;DR
- 暴力搜索枚举所有可能，简单但慢
- 记忆化／动态规划消除重复子问题
- 贪心在能成立时更快，但可能出错
- 同一个问题可以有多种解法，取决于利用了多少问题结构
正文
一路走来，我们认识了贪心、动态规划、回溯等好几种“设计算法的方法”。这一章把它们串成一条线，看看同一类问题，是怎样一步步变得更好的。
一条从慢到快的谱系
面对一个问题，可以有不同层次的解法：
- 暴力枚举：把所有可能都试一遍。简单、正确，但往往指数级，只能处理很小规模
- 回溯 + 剪枝：仍然枚举，但提前砍掉没希望的分支，比纯暴力高效
- 记忆化 / 动态规划：发现子问题重复，缓存结果，把指数级降为多项式级
- 贪心：如果问题结构足够好，每步选最优即可，通常最快
每一步的进步，来自对问题结构利用得更多：从“什么都不利用”，到“利用约束剪枝”，到“利用重叠子问题”，再到“利用最优子结构”。
但更快不等于更通用
这里有个关键提醒：越靠后的方法，适用范围往往越窄，正确性也越需要论证。
- 暴力枚举几乎万能，只是慢
- 动态规划要求重叠子问题与最优子结构
- 贪心最快，但经常不成立——上一章就专门讲了怎么证明或推翻它
所以，并不是“越快越好”。选哪种方法，取决于问题本身具备什么性质，以及你是否能证明它的正确性。一个用错前提的贪心，比老老实实的暴力枚举更糟，因为它可能悄悄给出错误答案。
选择，才是核心
这条谱系真正想教给我们的，不是四种具体方法，而是一种判断力：
面对新问题，先问——它有没有重复子问题？有没有最优子结构？能不能用约束把搜索剪小？贪心的直觉能不能被证明？
问清楚了，方法自然就浮现出来。这也正好引向整个部分的最后一章：没有万能的数据结构和算法，只有合适的取舍。
思考题 1
从暴力搜索到动态规划，改进的关键是什么？
思考题 2
既然贪心通常更快，为什么不能什么问题都用贪心？
小结
知识点
- 暴力枚举、回溯剪枝、动态规划、贪心构成一个谱系
- 进步源自对问题结构的更多利用
- 更快的方法通常适用范围更窄、更需论证
- 选择方法要先判断问题的性质
参考资料
- Wikipedia(zh)：算法设计：常见算法设计范式
- Wikipedia(zh)：动态规划：利用重叠子问题的改进方法
思考题答案（仅供参考）
思考题 1
关键在于发现并利用“重叠子问题”：暴力与回溯会反复计算同样的子问题，而动态规划把每个子问题的结果缓存起来、只算一次，从而把指数级的重复计算降为多项式级。
思考题 2
因为贪心并不总是正确。它只在“局部最优能导向全局最优”的问题上成立，而很多问题不具备这种性质。贸然使用贪心可能给出错误答案，因此必须先用证明或反例确认它的正确性。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪