区间 DP 总结

· · 个人记录

观前提醒： 此博客仅为我对区间 DP 的个人观点，如有错误或是误解，请您见谅或是提出问题，我将会积极改进此博客。

这玩意儿上限很高，下限也很高

做区间 DP = 烧脑子

\color{green}\mathtt {Level.1}\quad \mathtt{Easy Problem}

较为简单的区间 DP 一般状态设计较为简单，转移也仅仅只有区间分开再合并或是通过一定条件从该区间自身包含的区间着手，相当于按照题意进行模拟。

状态： 一般 dp[i][j] 表示区间 [i,j] 所能得到的 （题目要求所求）

转移：

特点：

Eg.1

P1063 [NOIP2006 提高组] 能量项链

特点： 环

此题可以说是区间 DP 入门题，状态： dp[i][j] 表示合并 [i,j]，能得到的最大价值。 转移： 对于一个区间：[l, r]，考虑它的合并情况：先合并 [l, k] 和 [k + 1, r]，再将这两个区间合并在一起，就能得到一种合并区间 [l, r] 的方案，由于 dp[l][k] 和 dp[k + 1][r] 都是最优情况下的合并，无需再去管它，所以 dp[i][j] 取 \max(dp[l][k] + dp[k + 1][r] + w[l] * w[k] * w[r]) 即可

Eg.2

P1040 [NOIP2003 提高组] 加分二叉树

特点： 模型转化

此题看似是一道图论的题，实际上由于中序遍历为 : 1,2,3,……,n。 可以将 dp[i][j] 设为 节点 i 到节点 j 可生成的子树最大价值为多少。 由于中序遍历根节点的左边一段为左子树，右边一段为右子树，所以考虑枚举该子树的根节点，所以 dp[i][j] = dp[i][k - 1] \times dp[k + 1][j] + a[k]。这同样可以理解为一个区间 DP。

\color{blue}\mathtt {Level.2}\quad \mathtt{Hard Problem}

较难的区间 DP，相较于简单区间 DP 的难度提升主要有两种：

  1. 状态设计：

对于一个区间，状态中不光为一个区间的左右端点，可能还要记录一些这个区间的特性。如 dp[i][j][1] 和 dp[i][j][2] 可能进行的转移不同。

  1. 转移：

此类问题中转移会涉及到一些复杂的判定能否转移，或者是转移时运用一些组合数学的知识。

感觉例题我讲不明白。

例一：[SCOI2003] 字符串折叠

P4302 [SCOI2003] 字符串折叠

难点： 转移

先考虑最朴素的状态设计 dp[i][j] 表示 [i,j] 最少能被折叠为多长。

转移：

  1. 区间分段，然后合并。显然，两个区间之间并不会互相影响，所以可以这么转移。

  2. 考虑折叠。由于此题数据范围很小，可以暴力枚举循环节，看看哪个可行，然后这个区间就可以压缩成 数字位数 + ( + 循环节长度 + ) 长度。但是观察样例可以发现：折叠是可以嵌套的，所以循环节仍然可以折叠，所以中间就不应该是循环节长度，而是 dp[ \mathsf{循环节}]。

例二：表达式的亿种可能

表达式的亿种可能

给定一个表达式，

每次你可以取出任意两个相邻的数字与它们之间的运算符 num_i ,opt_i,num_{i+1} ，优先进行计算再把运算结果放回。

在进行了 (n - 1) 轮上述操作后，可以得到该表达式的值。

容易发现共有 (n - 1) ! 种可能的计算顺序，求所有计算顺序得到的表达式的值之和。

难点： 转移

此题状态还是那个朴素的 dp[i][j] 表示计算 [num_i,num_j] 能得到的所有数的值的和。

但是，你会发现，计算顺序不同，得到的结果可能是一样的，但是值却只计算了一次。所以，每次转移还需要乘上一个常数。 **对于加法：** 左半部分每个结果都会与右半部分每个结果配对，所以每个数都要乘上右边的长度。 右半部分同理。 **对于减法：** 与加法同理 **对于乘法：** 可以理解为将一个序列顺序插入另一个排列的方案数。 即 $\frac {(r - l + 1)!}{len_{l}!len_{r}!}$。 > 参考：[区间dp总结 - 6a6q's blog](https://aaaaaaqqqqqq.top/index.php/archives/6/) ### **例三 P3736 [HAOI2016] 字符合并** [P3736 [HAOI2016] 字符合并](https://www.luogu.com.cn/problem/P3736) 由于合并要考虑形态，又因为一段区间合并之后最终长度是固定的（$len \bmod (k - 1)$）所以不妨将最终合并出来的状态也设进状态。 对于转移，只需考虑枚举断点将两个区间合并这种常规转移即可。 $dp_{l, r, s} = \max(dp_{l, k, s >> 1}，dp_{k +1, r, s \& 1})

注意

  1. 对于最终长度等于 1 的情况不能转移，所以转化为倒数第二个状态，最终再一合并转化回来，加上当前 k 位状态的值。

\color{gray}\mathtt {To \; sum \; up}

区间 DP，几乎没什么套路，全靠思维灵活度。