数据结构与算法 / 系统课时

判断一道题是否适合动态规划

判断一道题是否适合动态规划

动态规划不是“看到求最值就套模板”。本节给出一套判断顺序:先看问题能否用状态描述,再看子问题是否重复、答案能否组合,最后判断局部选择能否直接确定,从而在搜索、贪心和动态规划之间做选择。

学习目标

  • 能识别重叠子问题、最优子结构和阶段依赖三个关键信号。
  • 能区分适合搜索、贪心与动态规划的典型情形。
  • 能用一套固定检查顺序快速判断陌生题是否值得设计 dp 状态。

先看问题能否被状态描述

动态规划的起点不是数组,而是“状态”。一个状态应包含继续做决策所需的最少信息:只要这些信息相同,后续可选动作和最优答案就应相同。

例如“走到第 i 级台阶有多少种走法”里,当前位置 i 足以描述剩余问题;“背包还剩多少容量、已经考虑到第几个物品”则通常需要两个维度。反过来,如果必须记住完整操作历史才能判断下一步是否合法,状态可能很难压缩,直接搜索往往更自然。

用三个信号判断动态规划

重叠子问题说明不同选择会再次抵达同一个状态。暴力递归会重复计算这些状态,记忆化或自底向上计算才有明显收益。

最优子结构要求大问题的最优答案能由若干子问题的最优答案组合出来。例如打家劫舍中,“偷当前房屋”与“不偷当前房屋”分别依赖更小前缀的最优值,再取两者较大者。

阶段依赖意味着决策按位置、容量、区间长度等阶段推进,当前状态只依赖已经定义好的前驱状态。若状态之间没有稳定依赖顺序,设计 dp 表通常会很别扭。

搜索、贪心与动态规划的判断流程

为什么不是有重复就一定用动态规划

重叠只是“值得缓存”的信号,不等于题目一定适合经典动态规划。还要看状态数量是否可控,以及转移是否能完整覆盖答案。

搜索更适合状态空间本来就很小、约束复杂或需要枚举具体方案的题目。贪心更适合能够证明某个局部选择不会破坏全局最优的题目,例如按结束时间选择最多不重叠区间。动态规划则常见于“每一步有多个选择,不能只看眼前,但相同后续状态会反复出现”的问题。

快速决策清单

拿到陌生题时,可以按下面顺序检查:

  1. 尝试用少量变量描述“从现在开始还剩什么问题”。
  2. 想象暴力递归,不同分支是否会出现完全相同的调用参数。
  3. 检查当前答案是否能由更小状态的答案通过 min、max、求和、逻辑或等操作组合。
  4. 如果存在明显局部最优选择,先问自己能否证明它永远安全;能证明优先贪心,不能证明再保留多个选择做动态规划。
  5. 估算状态总数乘以每个状态的转移成本,确认复杂度能落在题目限制内。

真正决定是否使用动态规划的,不是题目长得像不像某个模板,而是能否定义有限状态、复用重复状态,并让答案沿稳定的依赖关系逐步计算出来。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

判断一道题是否适合动态规划

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通