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

按问题结构选择动态规划模型

按问题结构选择动态规划模型

没有“最长”“背包”“区间”之类关键词时,动态规划仍然可以系统建模。关键不是猜模板名称,而是观察问题如何分阶段推进、一次选择受到什么限制、当前答案依赖哪些更小问题,以及最终要求的是最值、计数还是可行性,再据此选择状态结构。

学习目标

  • 从阶段、选择约束、依赖结构和答案类型四个角度拆解题目
  • 根据结构判断更接近序列、背包、区间、树形或状态压缩 DP
  • 在多个模型都看似可用时,用状态含义和依赖关系排除错误建模

先找问题怎样向前推进

动态规划必须存在某种可以逐步扩展的“阶段”。阶段不一定是时间,也可以是已经处理的元素数量、区间长度、树的层级、已经选择的集合或当前容量。

若题目天然按照下标从左到右处理,状态通常会包含位置 i,容易形成序列 DP。若每加入一个物品都需要考虑剩余容量,则阶段是物品集合的处理进度,容量成为另一个状态维度。若问题要求从短区间组合成长区间,阶段往往是区间长度,对应区间 DP。

一个有效的状态应该让“已经处理的部分”与“还未处理的部分”形成清楚边界。若定义状态后仍然不知道下一步究竟推进哪个量,往往说明阶段还没有找对。

再看选择受到什么约束

同样是逐个处理元素,不同约束会产生完全不同的模型。选择一个元素之后,真正影响未来的不是完整历史,而是历史中仍会约束后续决策的那部分信息。

例如,“总重量不能超过容量”意味着未来只关心已经占用了多少容量,因此背包 DP 会记录容量;“相邻元素不能同时选”意味着未来只需要知道前一个元素是否被选;“某些对象是否已经使用过”则可能需要一个二进制集合记录选择历史,从而进入状态压缩 DP。

用依赖结构识别模型家族

状态定义之后,观察一个状态依赖哪些更小状态,往往比关键词更能暴露模型类型。

按问题结构选择动态规划模型的关系图

如果 dp[i] 只依赖较小下标,通常属于线性序列结构;如果 dp[l][r] 依赖更短的 [l, k]、[k+1, r],明显具有区间合并结构;如果父节点答案由若干子节点状态合并得到,则更接近树形 DP;如果 dp[mask] 依赖删除或加入某个元素后的集合,则核心结构是子集关系。

这一步还可以检查计算顺序。合法 DP 必须让依赖指向已经能够计算的状态。如果某个定义产生难以打破的循环依赖,通常不是简单调整遍历方向就能解决,而应重新判断状态是否缺少阶段信息。

最值、计数和可行性决定状态里存什么

问题结构决定“状态有哪些”,答案类型则决定“状态值是什么以及怎样合并”。这两个层次不要混在一起。

求最小代价时,状态值通常保存当前条件下的最小值,转移使用 min;求最大收益则使用 max;求方案数会把不同合法前驱的数量相加;只判断能否达到某个状态时,则保存布尔值并使用逻辑或。

因此,同一个背包结构既可以问最大价值,也可以问方案数或是否恰好装满。它们仍属于相同的阶段与容量模型,只是状态值和聚合运算不同。看到“求方案数”就单独寻找某个计数模板,反而容易忽略真正决定维度的选择约束。

多个模型都像时怎样排除

一道题可能同时出现序列、区间和选择限制,此时不要根据表面特征投票,而要比较哪种状态能够完整描述未来。

假设一次决策会把一个连续区间拆成左右两个独立子问题,那么区间边界通常必须进入状态,仅用当前位置 i 无法表达两个方向的剩余问题。反过来,如果从左到右处理后,过去元素不会再被访问,只留下一个累计容量或有限状态,那么保留整个区间显然是冗余的。

可以用四个问题快速核对模型:当前阶段是什么;哪些历史信息还会影响未来;一个状态依赖哪些更小状态;状态最终保存最值、计数还是可行性。四个答案能够相互吻合时,模型通常已经稳定。

把模板记忆改成结构识别

常见 DP 类型可以作为经验标签,但不应该成为建模起点。看到物品并不一定是背包,看到字符串也不一定是二维序列 DP,看到树也可能只需要普通递归。真正重要的是状态是否满足“信息足够但不过量”,以及转移是否只依赖规模更小、已经定义清楚的子问题。

训练时可以刻意先不写状态方程,只用一句话回答“处理到哪里”“未来还需要知道什么”“更小问题是什么”。当这三件事明确后,dp 的维度往往自然出现;再结合答案类型选择 min、max、求和或布尔聚合,就能在没有模板关键词时仍然找到可靠的动态规划入口。

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

目录与阅读设置

阅读设置

17

记录一个想法

按问题结构选择动态规划模型

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

登录哪都通