第二章:区间 DP

动态规划进阶目录 · 上一章:动态规划复习

1. 什么是区间 DP

区间动态规划(区间 DP)是动态规划中很常见的一类模型。它把原问题分解成若干个以连续区间为处理范围的子问题,先求较短区间的答案,再利用这些答案求出更长区间的答案。

例如,要把一整排石子合成一堆,可以先把左右两段分别合成一堆;要从一排数字的两端依次取数,取走一个端点后,又只剩一个更短的区间。原问题中的一次合并或一次选择,把需要处理的范围缩小了,较小的问题仍然可以继续求解。

上一章的背包按“前 ii 件物品”划分子问题。这里需要处理的部分,可能从序列中间开始,也可能在中间结束,因此通常用左右端点 l,rl,r 描述范围,用 fl,rf_{l,r} 保存区间 [l,r][l,r] 上某个问题的答案。保存的是最小代价、最大收益,还是其他结果,需要根据题意具体定义。

设计区间 DP 时,要先分析一次操作怎样留下更短的连续区间,再确定这些区间需要分别求出什么。状态规定较小问题,转移说明较小问题的答案怎样解决较大的问题。

2. 石子合并:把整排的合并问题缩小到任意一段

有 n≥1n\ge1 堆石子排成一行,第 ii 堆的重量为 ai>0a_i>0。每次合并相邻两堆,支付两堆重量之和,求合成一堆的最小总代价。

从第一次合并,转向观察最后一次合并

直接枚举第一次合并的两堆,可以继续搜索所有操作,但合并后的排列会发生变化。例如 [6,4,4,6][6,4,4,6],先合并左边两堆会变成 [10,4,6][10,4,6],先合并中间两堆则变成 [6,8,6][6,8,6]。此后面对的是不同的新排列,不能仅用“还剩几堆”描述剩余问题。

可以先观察一个始终成立的性质:每一堆石子都由原序列中的一段连续石堆合并而来。因为操作只允许合并相邻两堆,不会跳过中间的石子。

于是,最后一次合并前剩下的两堆,一定分别来自 [1,k][1,k] 与 [k+1,n][k+1,n]。只要知道这两段各自合成一堆的最小代价,就能加上最后一次合并的代价,得到这个分界下的最优结果。

完整问题由此缩小成两个规则相同的问题:分别把左右两段合成一堆。右边可能从 k+1k+1 开始,继续拆分时还会出现其他起点,所以需要求出任意连续段的答案。

状态保存一段石子合成一堆的最小代价

定义

fl,r=把原序列中第 l 至第 r 堆石子合成一堆的最小代价。f_{l,r}=\text{把原序列中第 }l\text{ 至第 }r\text{ 堆石子合成一堆的最小代价。}

状态中的两个端点限定了可使用的石子,目标“合成一堆”规定了子问题完成后的结果。无论内部怎样合并,最终这一堆的重量都等于原区间的总重量,因此后面的合并只需使用这段的最小代价。

先看 [4,2,3][4,2,3]。两堆合并时只有一次操作,所以 f1,2=6f_{1,2}=6,f2,3=5f_{2,3}=5。三堆的最后一次合并有两个分界:

最后一次合并前的两段先完成的较小问题总代价
[1,1][1,1] 与 [2,3][2,3]后两堆先合并,代价为 550+5+9=140+5+9=14
[1,2][1,2] 与 [3,3][3,3]前两堆先合并,代价为 666+0+9=156+0+9=15

无论分界在哪里,最后一次都支付总重量 99;不同选择影响的是此前两段的合并代价。因此 f1,3=14f_{1,3}=14。

枚举最后一个分界,得到状态转移

对于任意区间 [l,r][l,r],设最后一次合并前的两段为 [l,k][l,k] 与 [k+1,r][k+1,r]。

左边先用 fl,kf_{l,k} 合成一堆,右边先用 fk+1,rf_{k+1,r} 合成一堆。两段内部的操作互不影响,最后再支付整段重量。记

W(l,r)=∑i=lrai,W(l,r)=\sum_{i=l}^{r}a_i,

则有

fl,r=min⁡l≤k<r{fl,k+fk+1,r+W(l,r)}.f_{l,r}=\min_{l\le k<r} \{f_{l,k}+f_{k+1,r}+W(l,r)\}.

固定分界 kk 后,把任意一侧换成同一区间内代价更小的合并方案,都不会改变最后两堆的重量,也不会影响另一侧,所以两边可以分别取最优。再枚举所有分界,就覆盖了最后一次合并的全部可能。

从短区间开始求解

一个石堆已经是一堆,不需要操作,因此 fi,i=0f_{i,i}=0。长度至少为 22 的区间,先把最小代价设为 +∞+\infty,再逐一比较分界。

转移中的两个子区间都比 [l,r][l,r] 短,因此按长度递增计算。对于 [4,2,3][4,2,3],先求长度为 11 的三个初值,再求长度为 22 的 f1,2,f2,3f_{1,2},f_{2,3},最后才能比较完整区间的两个分界。

原题要求全部石子合成一堆,答案就是 f1,nf_{1,n}。共有 O(n2)O(n^2) 个区间,每个区间枚举 O(n)O(n) 个分界;用前缀和 S0=0S_0=0、Si=∑j=1iajS_i=\sum_{j=1}^{i}a_j,就能以 W(l,r)=Sr−Sl−1W(l,r)=S_r-S_{l-1} 在 O(1)O(1) 时间取得区间重量。总时间复杂度为 O(n3)O(n^3),空间复杂度为 O(n2)O(n^2)。

进一步手算:四堆石子,以及相邻最小值贪心的反例

对 [6,4,4,6][6,4,4,6],长度为 22 的答案为

f1,2=10,f2,3=8,f3,4=10.f_{1,2}=10,\qquad f_{2,3}=8,\qquad f_{3,4}=10.

长度为 33 时,f1,3=22f_{1,3}=22,f2,4=22f_{2,4}=22。长度为 44 时比较:

分界 kk候选代价
110+22+20=420+22+20=42
2210+10+20=4010+10+20=40
3322+0+20=4222+0+20=42

答案为 4040,对应先分别合并两端的 6,46,4,最后合并两堆重量为 1010 的石子。

若先贪心合并重量和最小的相邻两堆,就会先选中间的 4,44,4,随后支付 1414 与 2020,总代价为 8+14+20=428+14+20=42。第一次支付较少,不保证后续累计代价最小。

计算顺序:为什么不能按两个端点都递增填表

计算 f1,4f_{1,4} 时,可能需要 f2,4f_{2,4}。如果先固定 l=1l=1,再让 rr 从小到大,f2,4f_{2,4} 尚未计算,不能直接使用。

按长度递增能够同时保证左右两段先算完。另一种合法顺序是左端点递减、同一个左端点下右端点递增:左段 fl,kf_{l,k} 在本行较早的位置,右段 fk+1,rf_{k+1,r} 在已经完成的后面一行。计算顺序的依据是依赖关系。

3. 两端取数:区间也可以通过删除端点缩小

石子合并把大区间拆成两段。有些问题的一次选择只会留下一个更短的区间,仍然可以从较短区间的答案出发求解,但需要重新分析转移。

有 n≥1n\ge1 个正整数排成一行。每轮从最左端或最右端取走一个数,第 tt 轮取到的数乘以 tt 计入收益。全部取完,求最大总收益。

用剩余区间描述较小问题

每次都从端点取数,因此尚未取出的数字始终连续。无论已经取走了哪些端点,只要记下剩余部分的左右边界,就知道接下来能够选择哪两个数。

尝试定义

hl,r=原序列只剩区间 [l,r] 时,取完这些数字能够取得的最大后续收益。h_{l,r}=\text{原序列只剩区间 }[l,r]\text{ 时,取完这些数字能够取得的最大后续收益。}

但每个数的收益还与轮数有关,需要检查两个端点能否确定当前轮数。区间中剩下 r−l+1r-l+1 个数,而每轮恰好取走一个数,所以已经进行了 n−(r−l+1)n-(r-l+1) 轮,当前是

t=n−(r−l+1)+1.t=n-(r-l+1)+1.

轮数能够由区间长度得到,不需要独立增加一维。这个状态足以描述后续问题。

选择一个端点,使用剩余区间的答案

当前取左端 ala_l,本轮得到 talt a_l,剩余问题为 hl+1,rh_{l+1,r};取右端 ara_r,本轮得到 tart a_r,剩余问题为 hl,r−1h_{l,r-1}。因此对于 l<rl<r,有

hl,r=max⁡{tal+hl+1,r, tar+hl,r−1}.h_{l,r}=\max\{t a_l+h_{l+1,r},\ t a_r+h_{l,r-1}\}.

只剩一个数时,已经来到第 nn 轮,所以 hi,i=naih_{i,i}=n a_i。

以 [1,3,2][1,3,2] 为例,只剩后两个数 [3,2][3,2] 时处于第二轮。先取 33,收益为 2×3+3×2=122\times3+3\times2=12;先取 22,收益为 2×2+3×3=132\times2+3\times3=13,故 h2,3=13h_{2,3}=13。同样可以得到 h1,2=11h_{1,2}=11。

完整区间处于第一轮,所以

h1,3=max⁡{1+13, 2+11}=14.h_{1,3}=\max\{1+13,\ 2+11\}=14.

最优顺序是取 11、取 22、最后取 33。这里的子问题始终沿用原题的轮数,不能把剩余两个数重新当作从第一轮开始的一道新题。

虽然实际操作让区间越来越短,求答案时仍应先算短区间:只有较小问题已经得到答案,才知道当前选择哪个端点更优。按长度递增计算,最终取 h1,nh_{1,n}。共有 O(n2)O(n^2) 个状态,每个只比较两个候选,时间与整表空间复杂度均为 O(n2)O(n^2)。

4. 环形石子合并:改变起点后,继续使用线性区间

石子合并与两端取数,都把原序列中的连续段作为处理范围。如果石子首尾相邻地围成一个环,原来不连续的首尾两段也可以合并。此时先要解决的是怎样表示环上的连续范围。

例如 [1,10,10,1][1,10,10,1]。排成一行时,两个 11 不相邻;围成环后,首尾两个 11 可以先合并,再依次与两个 1010 合并,总代价为 2+12+22=362+12+22=36。只计算原排列的 f1,nf_{1,n},就无法考虑这个方案。

复制序列,表示跨过首尾的区间

从不同位置展开环,可以得到不同的线性排列。把原序列复制一份接到末尾,令 ai+n=aia_{i+n}=a_i,这些排列就都能表示成长度为 nn 的连续区间。

对于前面的例子,复制后得到

[1,10,10,1,1,10,10,1].[1,10,10,1,1,10,10,1].

其中区间 [3,6][3,6] 对应 [10,1,1,10][10,1,1,10],已经能够在线性排列中合并两个相邻的 11。

枚举展开位置,覆盖环上的合并方案

为什么枚举起点就足够?当环上最终只剩两堆时,它们分别来自两个连续弧段。沿其中一个分界把环剪开,此前两段内部的合并都不会跨过这个断点,因而整套操作可以在线性排列中完成。反过来,一种线性相邻合并方案也一定是环上的合法方案。

所以继续令 fl,rf_{l,r} 表示把这一段合成一堆的最小代价,沿用石子合并的转移。前缀和在复制后的序列上计算,区间长度只枚举到 nn;答案为

min⁡1≤l≤nfl,l+n−1.\min_{1\le l\le n}f_{l,l+n-1}.

每个候选都恰好包含原环上的每一堆石子一次。长度超过 nn,就会把复制出的同一堆重复使用,已经不再对应原问题。

初值仍为 fi,i=0f_{i,i}=0,按长度递增求解。区间数与分界枚举次数只增加常数倍,时间复杂度仍为 O(n3)O(n^3),空间复杂度为 O(n2)O(n^2)。只有一堆时无需合并,答案为 00。

进一步比较:为什么固定原来的起点会漏掉更优方案

在线性排列 [1,10,10,1][1,10,10,1] 中,最优方案是先分别合并两端的 1,101,10,总代价为 11+11+22=4411+11+22=44。

环上的最优值为 3636。这个更优方案在原排列中会跨过首尾边界,而在 [10,1,1,10][10,1,1,10] 中可以直接求出。复制序列解决跨界区间的表示,枚举起点则保证不会只考虑一个断点。

5. 三角剖分:区间的端点也可以表示区域边界

前面的区间描述一段石堆或剩余数字。进一步看,按顺序排列的顶点,也可以确定一块需要处理的区域。

给定一个凸多边形,顶点依次编号为 1,2,…,n1,2,\ldots,n,其中 n≥3n\ge3。第 ii 个顶点的权值为 wi>0w_i>0。用内部不相交的对角线划分三角形,每个三角形的代价为三个点权的乘积,求总代价的最小值。

用首尾之间的边界确定子多边形

选择连续顶点 l,l+1,…,rl,l+1,\ldots,r,再用线段 (l,r)(l,r) 把首尾连接起来,就得到一个较小的多边形。定义

gl,r=将顶点 l,l+1,…,r 对应的子多边形划分成三角形的最小代价。g_{l,r}=\text{将顶点 }l,l+1,\ldots,r\text{ 对应的子多边形划分成三角形的最小代价。}

需要找出完整剖分中哪个部分能把它分成较小区域。边 (l,r)(l,r) 内侧恰好与一个三角形相邻,设它的第三个顶点为 kk。去掉这个三角形后,两侧分别由顶点 l,…,kl,\ldots,k 与顶点 k,…,rk,\ldots,r 确定,仍然是两个较小的三角剖分问题。

因此,枚举这个顶点 kk:

gl,r=min⁡l<k<r{gl,k+gk,r+wlwkwr}.g_{l,r}=\min_{l<k<r} \{g_{l,k}+g_{k,r}+w_lw_kw_r\}.

两个子问题共享顶点 kk,因为分开的是区域,边界顶点可以共用,三角形却没有重复。石子合并中分开的是两组石堆,右边从 k+1k+1 开始;这里分开的是两块区域,右边从 kk 开始。子区间的端点必须对应实际剩下的对象。

在四边形上检查两个子问题

顶点权值为 [2,3,4,5][2,3,4,5] 时,固定边 (1,4)(1,4),第三个顶点可以选 22 或 33:

  • 选 22:新增三角形 (1,2,4)(1,2,4) 代价为 3030,另一侧三角形 (2,3,4)(2,3,4) 代价为 6060,合计 9090。
  • 选 33:新增三角形 (1,3,4)(1,3,4) 代价为 4040,另一侧三角形 (1,2,3)(1,2,3) 代价为 2424,合计 6464。

所以 g1,4=64g_{1,4}=64。固定与边 (l,r)(l,r) 相邻的三角形后,剩余两块区域可以分别剖分,选择各自的最优解不会影响新增三角形。

两个顶点只构成一条边,没有三角形,令 gi,i+1=0g_{i,i+1}=0。长度从 33 开始递增计算,较长区间初值为 +∞+\infty,答案为 g1,ng_{1,n}。每个区间枚举第三个顶点,时间复杂度为 O(n3)O(n^3),空间复杂度为 O(n2)O(n^2)。

为什么多边形需要是凸的

凸多边形中,连接两个顶点的对角线都位于多边形内部。任取 l<k<rl<k<r,三角形 (l,k,r)(l,k,r) 都能将对应区域合法地分开,所以可以直接枚举所有这样的 kk。

如果是一般的凹多边形,某些连接可能经过外部,不能直接套用这个转移,必须另外判断切分是否合法。

区间 DP 的分析从“整段问题怎样缩小”出发。合并石子需要选最后的分界,两端取数需要选下一次取走的端点,三角剖分需要选边界旁的三角形。只有先确定这些选择留下了什么,才能决定状态含义、子区间端点和转移中的新增代价。

6. 训练题单

讲解对应题

前三题对应正文中的线性合并、两端取数和环形合并。P1775、P1880 已在基础算法题单中安排,已经独立完成的题可以跳过。

顺序题目训练重点
1P1775 石子合并(弱化版)按最后一次合并确定分界,核对区间重量、初值和长度顺序
2P2858 Treats for the Cows从两端销售零食,由剩余数量确定天数,区分已得收益与后续收益
3P1880 石子合并复制环形序列、枚举起点,并分别求最小与最大合并代价

独立建模

这些题不能只更换石子合并的代价表达式,需要重新分析区间完成后的结果,以及哪些部分能够分别求解。

顺序题目训练重点
4P1435 回文字串按两端字符是否相同分类,将最少插入次数转成更短区间的问题
5P3146 248只有相等的两块才能合并;区分区间能否合成一块,以及最终答案是否必须覆盖整段
6P1063 能量项链用首尾标记描述合并结果,结合环形展开,重新确定最后一次释放的能量
7P1040 加分二叉树从中序连续段枚举根,处理空树与叶子的不同边界,并恢复前序遍历
8P4170 涂色后涂颜色可以覆盖前面,分析相同颜色能否共用一次操作,重新判断区间之间的关系

综合提高选做

最后四题分别增加当前位置、负数运算、重复结构和计数要求。先判断原来的两个端点是否足够,再决定需要补充哪些状态或转移。

顺序题目训练重点
9P1220 关路灯除已关灯的区间外,还要记录人在哪一端;移动期间所有未关灯都在耗电
10P4342 Polygon负数乘法要求同时保留区间最大值与最小值,最后输出所有能取得最优分数的断边
11P4302 字符串折叠同时考虑拼接与重复折叠,计入重复次数的位数和括号,并允许重复节继续折叠
12P3205 合唱队倒着分析两端插入过程,区分最后插入的是哪一端,并按题目要求统计方案数

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。