区间DP与树形DP：动态规划递推建模的进阶指南

如果你也在学动态规划大概率经历过这个阶段线性 DP、背包问题刷得还算顺手一碰到需要“枚举两个维度”“从子区间推导”“在树形结构上做决策”的题就懵。我自己的感受是动态规划学到中期最卡人的不是状态定义而是递推结构的建模方式。而区间 DP 和树形 DP恰好是两种最能拉开差距的递推范式。这篇博客对应我学习系列的 10~11 讲我把这两类 DP 放在一起写因为它们的核心思路惊人地一致——都是把一个大问题拆成由“结构边界”定义的子问题区别只在于边界长在区间上还是长在树上。如果你已经能把基础 DP 题写得比较顺但遇到“合并石子”“拆括号”“树上的分组分配”这类题目时迟迟找不到状态转移方程那这篇文章应该能帮你把思路打通。1. 从线性 DP 到区间 DP先想清楚“为什么状态要带两个端点”很多人刚开始学区间 DP 时最不习惯的一点是状态的定义突然变成了dp[l][r]而不是dp[i]。原因其实不复杂——当一个大问题的最优解需要由同一条序列上“任意两个位置之间”的那一段子问题组合而成时单靠一个位置是无法描述子问题的。拿最经典的“石子合并”来说一堆石子排成一排相邻的才能合并每次合并的代价是两堆石子的重量之和问最终合并成一堆的最小代价。如果只定义dp[i]表示“前 i 堆合并的最小代价”你会发现一个致命问题前 i 堆不一定真的能作为一个独立的合并区间因为合并必须发生在相邻的石子之间而前 i 堆和后边的堆在中间某个位置切分后左右两边各自合并的边界是悬空的。换句话说子问题必须是连续的一段区间而连续段就是用[l, r]来刻画的缺一个端点都不行。理解这一点之后区间 DP 的状态设计就有了方向dp[l][r] 将区间 [l, r] 内的元素按规则处理合并/计算/分割的最优值这个状态天然包含了两个维度也就意味着复杂度至少是 O(n²) 起步如果转移时还需要枚举中间分界点那就是 O(n³)。这也是为什么区间 DP 的题目一般 n 不会给太大通常在几百左右。回到石子合并的例子。设w[i]为第 i 堆的质量sum[i]为前缀和。那么区间[l, r]合并成一大堆的代价就等于把 [l, r] 分成左右两段分别合并再把左段和右段合并起来的代价加上合并这一下本身花的代价——而这一下付出的代价正好是sum[r] - sum[l-1]也就是整个区间的总重量。所以转移方程是dp[l][r] min(dp[l][k] dp[k1][r]) sum[r] - sum[l-1]k 从 l 到 r-1边界条件则是dp[i][i] 0因为单独一堆不需要合并。你看只要想通了“状态必须带两个端点”这个点递推方程几乎就是顺着题意写出来的反而是代码实现上有不少门道。1.1 三层循环的枚举顺序为什么长度必须放最外层这个问题我见过太多人踩坑包括我自己。区间 DP 的标准写法是三重循环但顺序不能随便排for length in range(2, n 1): # 枚举区间长度 for l in range(n - length 1): # 枚举左端点 r l length - 1 # 由长度和左端点算出右端点 dp[l][r] INF for k in range(l, r): # 枚举分割点 dp[l][r] min(dp[l][r], dp[l][k] dp[k 1][r]) dp[l][r] sum[r 1] - sum[l] # 如果转移时先加再取 min 也可以关键点是长度必须放在最外层。为什么因为dp[l][r]依赖的是长度比它更小的区间dp[l][k]和dp[k1][r]。如果外层枚举的是左端点当你在算dp[1][5]时dp[1][2]可能已经算完了但dp[2][5]还没算——因为它的左端点是 2而外层循环可能已经在处理左端点 1 了你根本没法保证所有需要的子区间都先于当前区间被算出来。这就像盖楼区间长度是楼层数必须先盖完矮楼层再去盖高楼层。外层枚举长度内层枚举左右端点才能保证每次转移时引用的子区间都是已经算好的。初始化方面要注意长度等于 1 的区间初始化为 0长度大于 1 的区间初始化为正无穷。如果你用 Python 写建议用[[INF] * n for _ in range(n)]而不是[[INF] * n] * n——后者会创建出共享引用的行改一个全变这是初学者很容易踩的隐形 bug。1.2 记忆化搜索是另一种实现方式但有个适用边界区间 DP 不只有循环写法也可以用递归 记忆化from functools import lru_cache lru_cache(None) def dfs(l, r): if l r: return 0 res INF for k in range(l, r): res min(res, dfs(l, k) dfs(k 1, r)) return res sum[r 1] - sum[l]这种写法更贴近“从大问题递归拆小问题”的自然思维适合状态转移方程复杂、顺序容易搞错的场景。但前提是你得保证递归深度不会爆栈n 在几百以内没问题如果区间规模上千甚至上万递归深度和函数调用开销就会成为瓶颈这时候老老实实用循环更稳。我的个人习惯是模拟题、地推题用循环写遇到那种状态维度多、边界条件复杂的题先用记忆化把思路验证一遍再改成循环优化这样不容易在没想清楚依赖顺序时写出 bug。2. 区间 DP 的经典范式与进阶优化环形、四边形不等式与状态压缩区间 DP 到后面会碰到三类非常典型的变体环形区间、代价函数可优化、状态需要额外维度。它们分别对应石子合并的环形版本、带权值的区间合并、以及括号序列或矩阵连乘这类题目。如果你只掌握了基础的三层循环碰到这三类题可能会直接卡住下面逐个拆。2.1 环形问题破环成链长度翻倍“石子合并”还有一个环形版本石子围成一圈合并规则不变求最小合并代价。处理手法非常经典——把环切成链并且复制一份接到原序列后面把长度变成 2n。具体做法是把原来的[0, n-1]复制一遍得到[n, 2n-1]然后对这个长度2n的序列做标准区间 DP最后在dp[i][in-1]里取最小值其中i从 0 到 n-1。这个dp[i][in-1]表示从环上的某个起点 i 开始沿环走一圈经过的 n 个元素构成的区间的最小合并代价。破环成链的本质是环上任意一种“断口”选法都等价于链上某个起点到起点n-1 的区间。枚举所有断口就能覆盖环的全部切分方案。这个方法不止适用于石子合并很多环形序列上的区间问题都可以照搬比如环形数组的最大子段和、环形 DNA 序列上的蛋白质折叠预测等。时间复杂度从 O(n³) 变成 O((2n)³) O(8n³)听起来增长了 8 倍但因为 n 通常不大几百以内实际还在可接受范围内。唯一要注意的是dp 数组至少要开 2n × 2n边界条件也要覆盖到 2n 的范围否则越界访问会给你带来非常难查的“假正确”结果——程序没崩但答案是错的。2.2 四边形不等式优化省掉一层枚举的经典手段三重循环 O(n³) 在 n 1000 时是十亿次运算Python 直接卡到怀疑人生。这时候就需要四边形不等式优化把时间复杂度降到 O(n²)。适用条件是转移方程形如dp[l][r] min(dp[l][k] dp[k1][r]) cost(l, r)且代价函数cost(l, r)满足四边形不等式和单调性。简单来说就是交叉区间代价不大于包含区间代价且区间越长代价越大。绝大多数“区间合并 区间和代价”的问题都满足这个性质石子合并就是典型。优化的核心结论是记录opt[l][r-1] opt[l][r] opt[l1][r]其中opt[l][r]是让dp[l][r]取到最小值的那个断点 k。于是第三层枚举 k 的范围可以缩小到[opt[l][r-1], opt[l1][r]]。for length in range(2, n 1): for l in range(n - length 1): r l length - 1 dp[l][r] INF for k in range(opt[l][r - 1], opt[l 1][r] 1): val dp[l][k] dp[k 1][r] sum[r 1] - sum[l] if val dp[l][r]: dp[l][r] val opt[l][r] k注意这里的边界opt[l][r-1]和opt[l1][r]必须已经在之前的迭代中算出来。这要求枚举顺序严格按区间长度从短到长因为opt[l][r-1]对应长度length-1而opt[l1][r]也对应长度length-1它们都比当前区间的长度短所以一定在更早的外层循环中就已经确定了。这个优化不是所有区间 DP 都能用。判定方法也很简单先用小规模数据暴力跑一遍再用优化版本跑一遍对比结果是否一致。如果一致再放心提交大测试点否则老老实实 O(n³)。在实际竞赛和面试中能用四边形不等式的题大概占区间 DP 的 30% 左右所以掌握它绝对是性价比很高的进阶投资。2.3 状态加维括号序列问题的核心套路有一类区间 DP 题光有dp[l][r]不够比如括号匹配、矩阵连乘、多边形剖分。拿最经典的“给字符串加括号使其成为合法括号序列”来说状态就需要增加一个维度表示“最外层是什么颜色的括号”。简单描述就是设dp[l][r][x][y]表示区间[l, r]以颜色 x 开头、颜色 y 结尾时的最小添加数或最大匹配数。转移分成两种一种是区间两端恰好匹配直接dp[l1][r-1]加上某种状态另一种是中间找一个断点把区间拆成两段分别处理。这类题的关键不在“加一维”本身难而在于你必须在状态设计阶段就想到两端的信息是重要的。一个常见的启发式判断如果区间两端元素之间存在“配对”或“排斥”关系且这种关系影响子问题的最小值那就应该在状态里保留一端或两端的信息。否则即使你强行转移也会发现遗漏了一部分合法情况。矩阵连乘则不太一样dp[l][r]表示矩阵链A[l] * A[l1] * ... * A[r]的最小乘法次数转移枚举的是“最后一次乘法”发生的位置。这里不需要加维因为矩阵的维度信息可以通过数组p[l]和p[r1]直接获得。从这两种不完全相同的处理方式可以看到区间 DP 的建模灵活性很大不能把所有题都往同一个状态模板里套。3. 动态规划 11 讲树形 DP 的递推方向与状态设计树形 DP 是另一个让很多人头疼的专题。它和区间 DP 一样本质上也是“由小结构推大结构”但小结构和大结构不是按数字大小排列的而是按树的父子关系排列的。搞清楚这一点树形 DP 的框架就清晰了一大半。3.1 为什么树形 DP 几乎都是后序遍历在树上做 DP最自然的思考方式是先算子树再算父节点。因为父节点的答案依赖所有子节点的答案子节点算完之前父节点是不可能算出正确答案的。这正好对应树的后序遍历DFS 先访问子节点再处理当前节点。一个最常见的入门例子是“树上的最大独立集”给一棵树每个节点有权值选一些节点使得任意两个被选节点之间没有直接边相连求最大权值之和。状态设计很直接dp[u][0] 以 u 为根的子树中不选 u 时的最大权值 dp[u][1] 以 u 为根的子树中选 u 时的最大权值转移分两组情况。如果不选 u那么子节点 v 选不选都可以取每个子节点两种状态的最大值加起来如果选 u那么子节点 v 一定不能选直接取dp[v][0]加起来。def dfs(u, parent): dp[u][0], dp[u][1] 0, val[u] for v in adj[u]: if v parent: continue dfs(v, u) dp[u][0] max(dp[v][0], dp[v][1]) dp[u][1] dp[v][0]注意这里有个细节DFS 时需要一个parent参数避免在无向树中往回走到父节点造成无限递归。有些初学者忽略这个参数结果程序要么栈溢出要么答案错得离谱。树形 DP 的 DFS 和普通 DFS 的最大区别就在这里——树是无向图必须显式区分父和子。3.2 树形 DP 的状态设计不只有选与不选当你刷树形 DP 超过十道题之后会发现“选与不选”只是最基础的二元状态。更常见的情况是需要在子节点之间做资源分配或者在每条边上做不同决策。比如“树的直径”问题——求树上最远两点之间的距离。一类经典做法是用dp[u]表示以 u 为根的子树中从 u 出发到子树内任意节点最长的路径长度。转移时每处理一个子节点 v就先用dp[u] dp[v] w(u, v)尝试更新直径再用dp[v] w(u, v)更新dp[u]。这里最容易犯的错误是顺序——必须先更新直径再更新dp[u]。如果先更新dp[u]那么计算直径时可能会把同一个子节点的两条路径接在一起形成一条虽然合法但实际上拐弯多于两次的路径。这个“顺序敏感性”是树形 DP 里一个非常隐蔽的坑。再看树上分组背包也叫树形背包每个节点可以选若干子节点每个子节点消耗一定容量、提供一定价值求总容量限制下的最大价值。这实际上是标准分组背包的树上版本只是“组”的概念变成了“一个子节点的所有可能分配方案”。状态设为dp[u][j] 以 u 为根的子树内容量为 j 时的最大价值转移时对每个子节点 v遍历 v 的容量 k再用dp[u][j - k] dp[v][k]更新dp[u][j]。复杂度表面上是O(n * m²)但仔细分析可以发现当一个子树大小为 sz每次只枚举到sz_v和当前已累计的容量时总复杂度可以控制在O(n * m)以内因为每个节点对只会被枚举一次。这个优化在实战中非常重要否则容量稍大一点就 TLE。3.3 换根 DP为什么需要两遍 DFS树形 DP 有一种进阶形式叫换根 DPrerooting DP典型题目是“求树上每个节点到所有其他节点的距离之和”。如果对每个节点都做一次树形 DP复杂度 O(n²)n 上万就完全不可行。换根 DP 用两遍 DFS 把复杂度降到 O(n)。核心思想先任选一个根比如节点 1做后序遍历得到dp[u]表示以 u 为根的子树内所有节点到 u 的距离之和。然后前序遍历从根往下推当根从 u 换到子节点 v 时v 的答案可以根据 u 的答案递推出来。递推公式是ans[v] ans[u] (n - sz[v]) - sz[v]解释一下这个公式的含义把根从 u 换到 vv 的子树内的所有节点共 sz[v] 个到根的距离都减少了 1所以总距离减少 sz[v]而 v 所在子树以外的节点共 n - sz[v] 个到根的距离都增加了 1所以总距离增加 n - sz[v]。两者合并就是上面的式子。换根 DP 的精髓是第一遍 DFS 算清以某个固定节点为根的“子树信息”第二遍 DFS 利用父子之间的递推关系把所有节点都当成根来算一遍。这个套路在最近几年的面试和竞赛中经常出现尤其是和树的重心、树的同构等知识结合起来考。4. 区间 DP 与树形 DP 的交叉点从石子合并到树上分配前面分别讲了区间 DP 和树形 DP可能有人会觉得这两个专题八竿子打不着。但实际刷题时会发现很多偏难的题恰恰是在两者交界处出出来的理解它们的共性反而能帮你快速定位建模方向。4.1 共用套路枚举“分界点”或“分配点”区间 DP 的核心操作是枚举分割点 k把区间[l, r]拆成左右两个子区间。树形 DP 的核心操作尤其树形背包是枚举子节点分配容量 k把一个子树拆成“之前的已处理儿子”和“当前儿子”两个部分。两者做的事情本质上都是尝试所有把大问题划分为两个独立子问题的切法只是“切”的对象不同一个是切一条线一个是切一棵树上的父子关系。如果你能养成“遇到问题先思考这个大问题可以怎样切分成两个独立子问题”的习惯那么区间 DP 和树形 DP 的入门门槛会大大降低。4.2 树上路径上的区间 DP有一种题是把区间 DP 搬到树上给一棵树每条边或每个节点有权值求从某个节点到另一个节点的路径上做“合并”操作的最小代价。这种情况往往需要先用树剖或 LCA 把路径转化成序列再做区间 DP。转化完之后区间 DP 的所有套路——长度枚举、断点枚举、环形破链等——都可以直接复用。这种交叉题的难点其实在**“把树上的路径转换成序列”这一步**因为你要清楚路径上的节点顺序等价于序列的下标顺序。如果这一步想不明白后面全都是白搭。我一般建议画一下样例的树结构手动模拟一次这条路径上的顺序关系再动手写代码。4.3 从树形背包到基础背包的退化树形背包有一个非常好的性质当树的形态变成一条链时它退化成普通的分组背包或 0/1 背包。反过来普通背包也可以理解为在一棵“虚拟树”上做决策只是每件物品的依赖关系变成了独立的节点。想通这一点你会发现在背包基础上加“依赖关系”的题本质上都是树形背包的变体。比如“选课问题”选某些课程必须先选它的先修课课程之间构成一棵森林。做法是把森林加一个虚拟根节点连成树然后做树形背包。虚拟根节点是树形依赖背包的经典技巧它能统一处理森林和多棵子树的情况把问题规约成单棵树代码简洁很多。5. 动态规划 10~11 实战案例环形石子合并的完整求解前面讲了不少理论现在我用一个完整的实战题目串起来题目就是“环形石子合并”因为这道题能把区间 DP 的循环顺序、环形破链、初始化、前缀和、以及最终答案枚举全部揉在一起。问题描述有 n 堆石子围成一个环第 i 堆石子重量为w[i]。每次选择相邻两堆合并成一堆合并代价为两堆重量之和。求把所有石子合并成一堆的最小总代价。def min_cost_stones(stones): n len(stones) nums stones * 2 # 破环成链 m len(nums) # 2n prefix [0] * (m 1) for i in range(m): prefix[i 1] prefix[i] nums[i] INF 10 ** 18 dp [[INF] * m for _ in range(m)] for i in range(m): dp[i][i] 0 # 单堆不需要合并 for length in range(2, n 1): # 只需枚举到 n因为环上的最长连续段是 n for l in range(m - length 1): r l length - 1 for k in range(l, r): cost dp[l][k] dp[k 1][r] prefix[r 1] - prefix[l] if cost dp[l][r]: dp[l][r] cost ans INF for i in range(n): ans min(ans, dp[i][i n - 1]) return ans这份代码有几个值得强调的点外层长度只枚举到 n而不是 2n。因为虽然数组长度是 2n但我们需要覆盖的区间长度最多是 n环上转一圈的元素个数更长的区间在物理意义上不存在。前缀和数组和 dp 数组都开到了 2n 的规模确保下标不会越界。答案枚举dp[i][in-1]的i从 0 到 n-1对应环上所有可能的断口。如果石子数量小于 500这个代码在 Python 下可以顺畅运行。如果 n 达到 1000就要考虑四边形不等式优化。实际做题时我建议先跑暴力版本得到正确答案再用优化版本提交这样能避免优化引入的边界错误。6. 这两讲学完我踩过的坑和调试心得最后分享几个我自己实际刷题过程中踩过的坑有些坑可以说是“不亲自踩一遍看题解根本意识不到”的。6.1 区间 DP 的“假正确”问题区间 DP 最常见的隐蔽 bug 是程序运行不报错小样例也过了但提交大测试点时答案错误。这种情况十有八九是循环顺序写反了。比如把左端点放在最外层、长度放在内层小数据因为状态偶然算全了能通过但数据一复杂就暴露出依赖顺序的错误。我的排查方法很朴素写一个debug_print(dp)函数把矩阵打印出来肉眼检查dp[l][r]是否在用dp[l][k]和dp[k1][r]时已经非 INF。如果出现 INF 参与比较那就是顺序问题果断调整循环嵌套。6.2 树形 DP 的递归深度与父节点遗漏树形 DP 的递归写法最容易崩在递归深度上。如果题目给的是链状树n 达到十万Python 默认递归深度大约 1000直接栈溢出。解决办法有两个一是sys.setrecursionlimit(1000000)粗暴调大二是改用栈 显式数组模拟后序遍历。另一个容易忽略的是“子节点可能本身就是父节点”的问题特别是无向树中。我吃过一次亏某次写树形背包DFS 时忘了传 parent导致程序在样例上直接死循环。加了if v parent: continue之后立刻正常。看起来是个小细节但真的会浪费你半小时。6.3 关于“先更新答案还是先更新状态”的顺序问题树形 DP 中最大直径这类问题ans的更新必须发生在用当前子节点更新dp[u]之前。原因是dp[u]必须先保存“从 u 出发、只经过之前已处理过的子节点的最长路径”然后和一个新子节点拼接成完整路径才能保证得到的是两条从同一节点出发但走向两个不同子树的路径。如果顺序反了dp[u]已经被新子节点更新过了再和同一个子节点拼一起就可能形成一条“从 u 到 v 再回到 u 再到另一个子孙节点”的非法路径。检查的方法也很简单用一个小树手推一遍看看直径是否可能重复计算了同一条边。6.4 不同语言的性能差异同样的 O(n³) 区间 DPC 能跑 n1000Python 只能跑 n500 左右。所以用 Python 做题时要更重视四边形不等式、环形破链后长度只枚举到 n 这类优化。如果你是为了面试准备动态规划我建议至少会一种编译型语言写快速版本不然遇到 dp 规模较大的题会比较吃力。我自己的体会是区间 DP 和树形 DP 就像 DP 学习路上的两级台阶。区间 DP 考验你对“子区间”的敏感度树形 DP 考验你画递归树和设计父子转移的能力。跨过这两关后面再学状态压缩 DP 和数位 DP思路会顺畅很多因为你会慢慢习惯“先建模、再写转移”的思考方式。最后再分享一个小技巧刷这一专题时每道题都先画一张小规模的示意图标出 dp 状态对应的区间或子树然后手动跑一遍样例。这个习惯看起来费时间但对建立直觉非常有帮助尤其是区间 DP 的断点枚举和树形 DP 的换根递推画着画着你就发现规律了。