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

判断一道题能否使用动态规划

判断一道题能否使用动态规划

很多题都有递归式,但递归式不等于动态规划。本节建立一套判断顺序:先看问题能否压缩成有限状态,再检查子问题是否重复、状态是否足够描述未来、答案是否能由子问题组合出来,最后决定该用暴力枚举、贪心还是 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 的问题,关键不是“能写递归”,而是能够找到一个足够小、无后效且可复用的状态集合,并让状态之间存在稳定的组合关系。

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

目录与阅读设置

阅读设置

17

记录一个想法

判断一道题能否使用动态规划

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

登录哪都通