数据结构与算法 / 系统课时
判断一道题能否使用动态规划
判断一道题能否使用动态规划
很多题都有递归式,但递归式不等于动态规划。本节建立一套判断顺序:先看问题能否压缩成有限状态,再检查子问题是否重复、状态是否足够描述未来、答案是否能由子问题组合出来,最后决定该用暴力枚举、贪心还是 DP。
学习目标
- 区分暴力枚举、贪心和动态规划各自依赖的条件
- 用重复子问题、无后效性与最优子结构判断 DP 的适用性
- 识别“存在递归关系但不值得做 DP”的问题
先区分三类解法
面对一个需要在多种选择中寻找答案的问题,暴力枚举、贪心和动态规划的差别不在代码长短,而在于它们允许丢弃多少搜索信息。
| 方法 | 核心做法 | 适用信号 |
|---|---|---|
| 暴力枚举 | 展开所有可能选择 | 状态规模很小,或暂时找不到可复用结构 |
| 贪心 | 每一步只保留当前看来最好的选择 | 能证明局部最优选择不会破坏全局最优解 |
| 动态规划 | 保存子问题答案并按状态关系组合 | 不同决策路径会反复到达相同子问题 |
例如用面值 1、3、4 凑出金额 6,若目标是最少硬币数,优先拿最大硬币的贪心会得到 4+1+1 共 3 枚,但最优答案是 3+3 共 2 枚。局部最优不能推出全局最优时,就需要继续寻找状态结构,而不能因为题目像“做选择”就直接套贪心。
动态规划需要的三个条件
重复子问题意味着不同选择路径会到达同一个子问题。若递归过程中 f(7) 被反复计算,只要它的答案确定,就有缓存并复用的价值。重复越明显,记忆化带来的收益通常越大。
无后效性不是说过去完全不重要,而是说过去对未来的影响已经被当前状态完整记录。若知道状态 s 后,后续决策还必须追问“你是怎么走到这里的”,说明状态信息不足,需要增加维度,而不是立即否定 DP。
最优子结构表示整体最优解能够由合适的子问题最优解组合得到。对于计数、可达性等非最优化问题,可以把它理解成更一般的“子问题答案可组合”:当前状态的答案能由更小状态的答案通过固定规则计算出来。

递归关系不等于动态规划
看到 f(n) 调用更小规模的 f(k),只能证明问题可以递归拆解,不能证明它适合 DP。归并排序同样有递归关系,但左右子数组基本互不重叠,保存已经完成的子问题不会消除大量重复计算,因此它属于分治而不是典型动态规划。
另一个常见误区是状态数量本身接近所有枚举结果。假设为了保证无后效性,不得不把完整选择历史都放进状态,那么即使写出了转移关系,状态空间仍可能呈指数增长。这种写法形式上像 DP,却没有真正压缩搜索空间。
用判断清单落地
拿到新题时,可以按固定顺序检查:先尝试用少量变量描述“一个子问题是什么”;再确认这些变量是否已经包含影响未来的全部信息;随后观察不同选择是否会到达相同状态;最后写出当前状态怎样由更小状态组合得到。
如果还存在明显的局部最优选择,再额外问一句:这个选择能否通过交换论证、单调性或其他严格理由保证全局最优?能够证明时,贪心通常比 DP 更简单;无法证明时,不应仅凭直觉丢弃其他候选状态。
真正值得设计 DP 的问题,关键不是“能写递归”,而是能够找到一个足够小、无后效且可复用的状态集合,并让状态之间存在稳定的组合关系。