第二章:区间 DP

1. 什么是区间 DP
区间动态规划(区间 DP)是动态规划中很常见的一类模型。它把原问题分解成若干个以连续区间为处理范围的子问题,先求较短区间的答案,再利用这些答案求出更长区间的答案。
例如,要把一整排石子合成一堆,可以先把左右两段分别合成一堆;要从一排数字的两端依次取数,取走一个端点后,又只剩一个更短的区间。原问题中的一次合并或一次选择,把需要处理的范围缩小了,较小的问题仍然可以继续求解。
上一章的背包按“前 件物品”划分子问题。这里需要处理的部分,可能从序列中间开始,也可能在中间结束,因此通常用左右端点 描述范围,用 保存区间 上某个问题的答案。保存的是最小代价、最大收益,还是其他结果,需要根据题意具体定义。
设计区间 DP 时,要先分析一次操作怎样留下更短的连续区间,再确定这些区间需要分别求出什么。状态规定较小问题,转移说明较小问题的答案怎样解决较大的问题。
2. 石子合并:把整排的合并问题缩小到任意一段
有 堆石子排成一行,第 堆的重量为 。每次合并相邻两堆,支付两堆重量之和,求合成一堆的最小总代价。
从第一次合并,转向观察最后一次合并
直接枚举第一次合并的两堆,可以继续搜索所有操作,但合并后的排列会发生变化。例如 ,先合并左边两堆会变成 ,先合并中间两堆则变成 。此后面对的是不同的新排列,不能仅用“还剩几堆”描述剩余问题。
可以先观察一个始终成立的性质:每一堆石子都由原序列中的一段连续石堆合并而来。因为操作只允许合并相邻两堆,不会跳过中间的石子。
于是,最后一次合并前剩下的两堆,一定分别来自 与 。只要知道这两段各自合成一堆的最小代价,就能加上最后一次合并的代价,得到这个分界下的最优结果。
完整问题由此缩小成两个规则相同的问题:分别把左右两段合成一堆。右边可能从 开始,继续拆分时还会出现其他起点,所以需要求出任意连续段的答案。
状态保存一段石子合成一堆的最小代价
定义
状态中的两个端点限定了可使用的石子,目标“合成一堆”规定了子问题完成后的结果。无论内部怎样合并,最终这一堆的重量都等于原区间的总重量,因此后面的合并只需使用这段的最小代价。
先看 。两堆合并时只有一次操作,所以 ,。三堆的最后一次合并有两个分界:
| 最后一次合并前的两段 | 先完成的较小问题 | 总代价 |
|---|---|---|
| 与 | 后两堆先合并,代价为 | |
| 与 | 前两堆先合并,代价为 |
无论分界在哪里,最后一次都支付总重量 ;不同选择影响的是此前两段的合并代价。因此 。
枚举最后一个分界,得到状态转移
对于任意区间 ,设最后一次合并前的两段为 与 。
左边先用 合成一堆,右边先用 合成一堆。两段内部的操作互不影响,最后再支付整段重量。记
则有
固定分界 后,把任意一侧换成同一区间内代价更小的合并方案,都不会改变最后两堆的重量,也不会影响另一侧,所以两边可以分别取最优。再枚举所有分界,就覆盖了最后一次合并的全部可能。
从短区间开始求解
一个石堆已经是一堆,不需要操作,因此 。长度至少为 的区间,先把最小代价设为 ,再逐一比较分界。
转移中的两个子区间都比 短,因此按长度递增计算。对于 ,先求长度为 的三个初值,再求长度为 的 ,最后才能比较完整区间的两个分界。
原题要求全部石子合成一堆,答案就是 。共有 个区间,每个区间枚举 个分界;用前缀和 、,就能以 在 时间取得区间重量。总时间复杂度为 ,空间复杂度为 。
进一步手算:四堆石子,以及相邻最小值贪心的反例
对 ,长度为 的答案为
长度为 时,,。长度为 时比较:
| 分界 | 候选代价 |
|---|---|
答案为 ,对应先分别合并两端的 ,最后合并两堆重量为 的石子。
若先贪心合并重量和最小的相邻两堆,就会先选中间的 ,随后支付 与 ,总代价为 。第一次支付较少,不保证后续累计代价最小。
计算顺序:为什么不能按两个端点都递增填表
计算 时,可能需要 。如果先固定 ,再让 从小到大, 尚未计算,不能直接使用。
按长度递增能够同时保证左右两段先算完。另一种合法顺序是左端点递减、同一个左端点下右端点递增:左段 在本行较早的位置,右段 在已经完成的后面一行。计算顺序的依据是依赖关系。
3. 两端取数:区间也可以通过删除端点缩小
石子合并把大区间拆成两段。有些问题的一次选择只会留下一个更短的区间,仍然可以从较短区间的答案出发求解,但需要重新分析转移。
有 个正整数排成一行。每轮从最左端或最右端取走一个数,第 轮取到的数乘以 计入收益。全部取完,求最大总收益。
用剩余区间描述较小问题
每次都从端点取数,因此尚未取出的数字始终连续。无论已经取走了哪些端点,只要记下剩余部分的左右边界,就知道接下来能够选择哪两个数。
尝试定义
但每个数的收益还与轮数有关,需要检查两个端点能否确定当前轮数。区间中剩下 个数,而每轮恰好取走一个数,所以已经进行了 轮,当前是
轮数能够由区间长度得到,不需要独立增加一维。这个状态足以描述后续问题。
选择一个端点,使用剩余区间的答案
当前取左端 ,本轮得到 ,剩余问题为 ;取右端 ,本轮得到 ,剩余问题为 。因此对于 ,有
只剩一个数时,已经来到第 轮,所以 。
以 为例,只剩后两个数 时处于第二轮。先取 ,收益为 ;先取 ,收益为 ,故 。同样可以得到 。
完整区间处于第一轮,所以
最优顺序是取 、取 、最后取 。这里的子问题始终沿用原题的轮数,不能把剩余两个数重新当作从第一轮开始的一道新题。
虽然实际操作让区间越来越短,求答案时仍应先算短区间:只有较小问题已经得到答案,才知道当前选择哪个端点更优。按长度递增计算,最终取 。共有 个状态,每个只比较两个候选,时间与整表空间复杂度均为 。
4. 环形石子合并:改变起点后,继续使用线性区间
石子合并与两端取数,都把原序列中的连续段作为处理范围。如果石子首尾相邻地围成一个环,原来不连续的首尾两段也可以合并。此时先要解决的是怎样表示环上的连续范围。
例如 。排成一行时,两个 不相邻;围成环后,首尾两个 可以先合并,再依次与两个 合并,总代价为 。只计算原排列的 ,就无法考虑这个方案。
复制序列,表示跨过首尾的区间
从不同位置展开环,可以得到不同的线性排列。把原序列复制一份接到末尾,令 ,这些排列就都能表示成长度为 的连续区间。
对于前面的例子,复制后得到
其中区间 对应 ,已经能够在线性排列中合并两个相邻的 。
枚举展开位置,覆盖环上的合并方案
为什么枚举起点就足够?当环上最终只剩两堆时,它们分别来自两个连续弧段。沿其中一个分界把环剪开,此前两段内部的合并都不会跨过这个断点,因而整套操作可以在线性排列中完成。反过来,一种线性相邻合并方案也一定是环上的合法方案。
所以继续令 表示把这一段合成一堆的最小代价,沿用石子合并的转移。前缀和在复制后的序列上计算,区间长度只枚举到 ;答案为
每个候选都恰好包含原环上的每一堆石子一次。长度超过 ,就会把复制出的同一堆重复使用,已经不再对应原问题。
初值仍为 ,按长度递增求解。区间数与分界枚举次数只增加常数倍,时间复杂度仍为 ,空间复杂度为 。只有一堆时无需合并,答案为 。
进一步比较:为什么固定原来的起点会漏掉更优方案
在线性排列 中,最优方案是先分别合并两端的 ,总代价为 。
环上的最优值为 。这个更优方案在原排列中会跨过首尾边界,而在 中可以直接求出。复制序列解决跨界区间的表示,枚举起点则保证不会只考虑一个断点。
5. 三角剖分:区间的端点也可以表示区域边界
前面的区间描述一段石堆或剩余数字。进一步看,按顺序排列的顶点,也可以确定一块需要处理的区域。
给定一个凸多边形,顶点依次编号为 ,其中 。第 个顶点的权值为 。用内部不相交的对角线划分三角形,每个三角形的代价为三个点权的乘积,求总代价的最小值。
用首尾之间的边界确定子多边形
选择连续顶点 ,再用线段 把首尾连接起来,就得到一个较小的多边形。定义
需要找出完整剖分中哪个部分能把它分成较小区域。边 内侧恰好与一个三角形相邻,设它的第三个顶点为 。去掉这个三角形后,两侧分别由顶点 与顶点 确定,仍然是两个较小的三角剖分问题。
因此,枚举这个顶点 :
两个子问题共享顶点 ,因为分开的是区域,边界顶点可以共用,三角形却没有重复。石子合并中分开的是两组石堆,右边从 开始;这里分开的是两块区域,右边从 开始。子区间的端点必须对应实际剩下的对象。
在四边形上检查两个子问题
顶点权值为 时,固定边 ,第三个顶点可以选 或 :
- 选 :新增三角形 代价为 ,另一侧三角形 代价为 ,合计 。
- 选 :新增三角形 代价为 ,另一侧三角形 代价为 ,合计 。
所以 。固定与边 相邻的三角形后,剩余两块区域可以分别剖分,选择各自的最优解不会影响新增三角形。
两个顶点只构成一条边,没有三角形,令 。长度从 开始递增计算,较长区间初值为 ,答案为 。每个区间枚举第三个顶点,时间复杂度为 ,空间复杂度为 。
为什么多边形需要是凸的
凸多边形中,连接两个顶点的对角线都位于多边形内部。任取 ,三角形 都能将对应区域合法地分开,所以可以直接枚举所有这样的 。
如果是一般的凹多边形,某些连接可能经过外部,不能直接套用这个转移,必须另外判断切分是否合法。
区间 DP 的分析从“整段问题怎样缩小”出发。合并石子需要选最后的分界,两端取数需要选下一次取走的端点,三角剖分需要选边界旁的三角形。只有先确定这些选择留下了什么,才能决定状态含义、子区间端点和转移中的新增代价。
6. 训练题单
讲解对应题
前三题对应正文中的线性合并、两端取数和环形合并。P1775、P1880 已在基础算法题单中安排,已经独立完成的题可以跳过。
| 顺序 | 题目 | 训练重点 |
|---|---|---|
| 1 | P1775 石子合并(弱化版) | 按最后一次合并确定分界,核对区间重量、初值和长度顺序 |
| 2 | P2858 Treats for the Cows | 从两端销售零食,由剩余数量确定天数,区分已得收益与后续收益 |
| 3 | P1880 石子合并 | 复制环形序列、枚举起点,并分别求最小与最大合并代价 |
独立建模
这些题不能只更换石子合并的代价表达式,需要重新分析区间完成后的结果,以及哪些部分能够分别求解。
| 顺序 | 题目 | 训练重点 |
|---|---|---|
| 4 | P1435 回文字串 | 按两端字符是否相同分类,将最少插入次数转成更短区间的问题 |
| 5 | P3146 248 | 只有相等的两块才能合并;区分区间能否合成一块,以及最终答案是否必须覆盖整段 |
| 6 | P1063 能量项链 | 用首尾标记描述合并结果,结合环形展开,重新确定最后一次释放的能量 |
| 7 | P1040 加分二叉树 | 从中序连续段枚举根,处理空树与叶子的不同边界,并恢复前序遍历 |
| 8 | P4170 涂色 | 后涂颜色可以覆盖前面,分析相同颜色能否共用一次操作,重新判断区间之间的关系 |
综合提高选做
最后四题分别增加当前位置、负数运算、重复结构和计数要求。先判断原来的两个端点是否足够,再决定需要补充哪些状态或转移。
| 顺序 | 题目 | 训练重点 |
|---|---|---|
| 9 | P1220 关路灯 | 除已关灯的区间外,还要记录人在哪一端;移动期间所有未关灯都在耗电 |
| 10 | P4342 Polygon | 负数乘法要求同时保留区间最大值与最小值,最后输出所有能取得最优分数的断边 |
| 11 | P4302 字符串折叠 | 同时考虑拼接与重复折叠,计入重复次数的位数和括号,并允许重复节继续折叠 |
| 12 | P3205 合唱队 | 倒着分析两端插入过程,区分最后插入的是哪一端,并按题目要求统计方案数 |
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…