在输入为长度为 n 的数组时，子问题用区间 [i..j] 表示。

状态的定义和转移都与区间有关，称为区间动态规划

区间动态规划简介

区间 DP 是状态的定义和转移都与区间有关，其中区间用两个端点表示。

状态定义 dp[i][j] = [i..j] 上原问题的解。i 变大，j 变小都可以得到更小规模的子问题。

对于单串上的问题，我们可以对比一下线性动态规划和区间动态规划。线性动态规划, 一般是定义 dp[i]， 表示考虑到前 i 个元素，原问题的解，i 变小即得到更小规模的子问题，推导状态时候是从前往后，即 i 从小到大推的。区间动态规划，一般是定义 dp[i][j]，表示考虑 [i..j] 范围内的元素，原问题的解增加 i，减小 j 都可以得到更小规模的子问题。推导状态一般是按照区间长度从短到长推的。

区间动态规划的状态设计，状态转移都与线性动态规划有明显区别，但是由于这两种方法都经常用在单串问题上，拿到一个单串的问题时，往往不能快速地判断到底是用线性动态规划还是区间动态规划，这也是区间动态规划的难点之一。

状态转移，推导状态 dp[i][j] 时，有两种常见情况

dp[i][j] 仅与常数个更小规模子问题有关

一般是与 dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1] 有关。

dp[i][j] = f(dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1])

代码常见写法

for len = 1..n
    for i = i..len
        j = i + len - 1
        dp[i][j] = max(dp[i][j], f(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]))

时间复杂度和空间复杂度均为 \(O(n^{2})\)

dp[i][j] 与 O(n) 个更小规模子问题有关

一般是枚举 [i,j] 的分割点，将区间分为 [i,k] 和 [k+1,j]，对每个 k 分别求解（下面公式的 f），再汇总（下面公式的 g）。

dp[i][j] = g(f(dp[i][k], dp[k + 1][j])) 其中 k = i .. j-1。

代码常见写法, 以下代码以 f 为 max 为例

for len = 1..n
    for i = i..len
        j = i + len - 1
        for k = i..j
            dp[i][j] = max(dp[i][j], f(dp[i][k], dp[k][j]))

时间复杂度可以达到 \(O(n^3)\)，空间复杂度还是 \(O(n^2)\)

区间动态规划经典问题

大规模问题与常数个小规模问题有关

最常见的形式如下：

推导 dp[i][j] 时，需要用到 dp[i][j-1], dp[i+1][j], dp[i+1][j-1] 三个子问题

• 最长回文子序列

考虑一个字符串 s 的所有子序列, 这些子序列中最长的回文子序列长度是多少

这个问题如果用线性动态规划的经典思路，状态如下：

dp[i] := 考虑 [0..i] , 原问题的答案

但是此后我们就遇到了困难，会发现这个状态有些难以转移

而如果考虑区间动态规划，状态如下：

dp[i][j] := 区间 [i..j] 上, 原问题的答案

转移的时候，考虑 dp[i][j-1], dp[i+1][j], dp[i+1][j-1] 这三个子问题，这是考虑把边界去掉的模式，回文的特点恰好时候这种模式，

根据两个边界的元素关系可以得到转移方程如下：

dp[i][j] = dp[i + 1][j - 1] + 2;                if (s[i] == s[j])
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);     if (s[i] != s[j])

回文是用区间动态规划解决的常见问题，有很多变种，下一节中列出的练习题有很多类似的。

大规模问题与 O(n) 个小规模问题有关

推导 dp[i][j] 时，需要 [i..j] 的所有子区间信息，其中子区间的其中一个端点与原区间重合，共 O(n) 个子区间

最常见的形式

dp[i][j] = g(f(dp[i][k], dp[k][j])) 其中 k = i+1 .. j-1。

其中 g 常见的有 max/min，例如 664 就是 min

下面就以 664 题讲解这种模式的思考方式

==【奇怪的打印机】==

有台奇怪的打印机有以下两个特殊要求： 打印机每次只能打印同一个字符序列。 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。 给定一个只包含小写英文字母的字符串 s，你的任务是计算这个打印机打印它需要的最少次数。

首先区间动态规划的状态定义与前面一样，还是经典的定义方式，状态定义模式化这也是区间动态规划的一个特点。

dp[i][j] := 打印出 [i..j] 上的字符需要的最少次数

在转移时，枚举中间的切分位置 k，考虑 i 边界以及中间枚举的切分位置 k 转移时的情况

i 要自己涂一次，则 dp[i][j] = 1 + dp[i + 1][j]

其中第一项 1 表示 i 位置单独花费一次次数 i 与中间的某个切分位置 k 一起打印 (条件是 s[i] = s[k])，则 dp[i][j] = dp[i+1][k] + dp[k+1][j]

其中第一项 dp[i+1][k] 表示 i 位置跟着 k 一起转移了，不在单独考虑 i 花费的次数了

综合以上分析可以写出状态转移方程如下：

dp[i][j] = dp[i + 1][j] + 1;
dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]); 其中 i < k <= j 且 s[i] == s[k]

区间动态规划回文相关问题

• 最长回文子串
• 回文子串
• 最长回文子序列
• 段式回文
• 统计不同回文子字符串
• 让字符串成为回文串的最少插入次数 —— 最长回文子序列

区间动态规划其它问题

• 戳气球
• 移除盒子 —— 戳气球升级版，[i][j] 基础上加了一维 k 状态，k 是 j 右侧与 j 相同的元素个数, 记忆化
• 多边形三角剖分的最低得分
• 奇怪的打印机
• 合并石头的最低成本
• 预测赢家
• 编码最短长度的字符串

区间动态规总结

区间动态规划一般用在单串问题上，以区间 [i, j] 为单位思考状态的设计和转移。它与线性动态规划在状态设计和状态转移上都有明显的不同，但由于这两个方法都经常用在单串问题上，导致我们拿到一个单串的问题时，经常不能快速反映出应该用哪种方法。这是区间动态规划的难点之一，但是这个难点也是好解决的，就是做一定数量的练习题，因为区间动态规划的题目比线性动态规划少很多，并且区间动态规划的状态设计和转移都比较朴素，变化也比线性动态规划少很多，所以通过不多的题目数量就可以把区间动态规划常见的方法和变化看个大概了。

推荐阅读顺序

1. 数据结构与算法 - 动态规划（简介）
2. 数据结构与算法 - 动态规划（线性动态规划）
3. 数据结构与算法 - 动态规划（前缀和）
4. 数据结构与算法 - 动态规划（区间动态规划）
5. 数据结构与算法 - 动态规划（背包问题）
6. 数据结构与算法 - 动态规划（状态压缩）
7. 数据结构与算法 - 动态规划（计数问题）
8. 数据结构与算法 - 矩阵快速幂
9. 数据结构与算法 - 动态规划（数位动态规划）