区间DP

前言

上一篇 LIS、LCS 与编辑距离 里，最长回文子序列已经用到了一种特殊的状态——$dp[l][r]$ 表示”区间 $[l, r]$ 上的最优解”。这种按区间定义状态、从小区间推导大区间的 DP，就是区间 DP。

区间 DP 的应用场景很广。比如：把一串数字按相邻对删掉，最小代价是多少？给一串括号，最少补几个才能匹配？把若干矩阵相乘，怎样加括号使得乘法次数最少？这些问题都共享同一个结构——在某处切一刀，左半边和右半边各自最优，再合并。

问题的本质

为什么普通 DP 不够用？

之前遇到的 DP，状态都是”前 $i$ 个”或”容量 $j$“——状态沿着一个方向增长。但有些问题的状态天然是一个区间。比如回文子序列，$S[l]$ 和 $S[r]$ 能不能匹配取决于两端字符，不是”前缀”能描述的。

区间 DP 的核心思想：先解决所有小区间的最优解，再逐步扩大区间长度。计算顺序是按区间长度从小到大，不是按位置从左到右。

通用框架

$dp[l][r]$ = 区间 $[l, r]$ 上的最优值。枚举分割点 $k \in [l, r)$：

$dp[l][r] = \min_{k} (dp[l][k] + dp[k+1][r] + \text{合并代价})$

// 初始化：长度为 1 的区间
for (int i = 0; i < N; i++) dp[i][i] = 初始值;

// 按区间长度从小到大枚举
for (int len = 2; len <= N; len++)           // ① 先算短区间
    for (int l = 0; l + len - 1 < N; l++) {  // ② 枚举左端点
        int r = l + len - 1;                  // ③ 右端点
        for (int k = l; k < r; k++)           // ④ 枚举分割点
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost);
    }

逐行解析：

• ① 区间长度必须从小到大。因为计算长度为 $len$ 的区间时，需要用到所有长度 $< len$ 的区间的结果。
• ②③ 给定长度 $len$ 和左端点 $l$，右端点 $r = l + len - 1$ 就确定了。
• ④ 在 $[l, r]$ 内枚举分割点 $k$，把区间分成 $[l, k]$ 和 $[k+1, r]$ 两半。两半各自已经算好了，加上合并代价就是总代价。

时间复杂度 $O(N^3)$（$N$ 个左端点 $\times$ $N$ 个右端点 $\times$ $N$ 个分割点）。$N \le 500$ 以内可以接受。

理论 + 代码

模型一：相邻配对删除

给定 $2N$ 个数排成一排。每次删相邻两个数，代价是 $|A_i - A_{i+1}|$。删完所有数的最小总代价？

这不是简单的贪心——每次删最小代价的相邻对可能导致后续配对变差。

状态：$dp[l][r]$ = 把区间 $[l, r]$ 中的数全部删掉的最小代价。

转移：枚举 $l$ 和谁配对。如果 $l$ 和 $k$ 配对（$l < k \le r$），代价是 $|A_l - A_k|$，然后 $[l+1, k-1]$ 和 $[k+1, r]$ 各自删完：

$dp[l][r] = \min_{k=l+1,l+3,\ldots} (|A_l - A_k| + dp[l+1][k-1] + dp[k+1][r])$

注意 $k$ 的奇偶性：$l$ 和 $k$ 之间有奇数个元素时才能全部配对，所以 $k - l$ 必须是奇数。

模型二：回文子序列（区间 DP 版）

上一篇已经讲过。$dp[l][r]$ = 子串 $S[l \ldots r]$ 的最长回文子序列长度。

• $S[l] = S[r]$：$dp[l][r] = dp[l+1][r-1] + 2$
• $S[l] \ne S[r]$：$dp[l][r] = \max(dp[l+1][r],\ dp[l][r-1])$

模型三：矩阵链乘法

$N$ 个矩阵 $M_1, M_2, \ldots, M_N$，$M_i$ 大小 $r_i \times c_i$，且 $c_i = r_{i+1}$。求最少乘法次数。

状态：$dp[l][r]$ = 矩阵 $M_l$ 到 $M_r$ 相乘的最少乘法次数。

转移：最后一步一定是某次乘法把 $[l, k]$ 和 $[k+1, r]$ 合并：

$dp[l][r] = \min_{l \le k < r} (dp[l][k] + dp[k+1][r] + r_l \times c_k \times c_r)$

其中 $r_l \times c_k \times c_r$ 是最后那次矩阵乘法的代价。

例题

例题 1：T90 019 — Pick Two（★6，相邻配对删除）

题目：长度 $2N$ 的数列 $A$。每次选相邻两个数删掉，代价 $|A_i - A_{i+1}|$。重复 $N$ 次删完所有数。求最小总代价。

数据范围：$1 \le N \le 15$，$1 \le A_i \le 10^5$

—— AtCoder Typical 90 019

分析：$2N \le 30$，$O(N^3)$ 的区间 DP 绰绰有余。

状态 $dp[l][r]$ = 把 $A[l \ldots r]$ 全部删完的最小代价。$r - l + 1$ 必须是偶数（每次删 2 个）。

转移：枚举 $l$ 和谁配对。配对后，中间和右边各自独立删除。

输入样例：

3
6 2 3 9 8 6

输出：2

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int A[36], dp[36][36];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < 2 * N; i++) scanf("%d", &A[i]);

    for (int i = 0; i < 2 * N; i++)
        for (int j = 0; j < 2 * N; j++) dp[i][j] = INF;
    for (int i = 0; i < 2 * N; i++) dp[i][i] = 0;   // ① 单个元素无法删除

    // ② 按区间长度枚举（只考虑偶数长度）
    for (int len = 2; len <= 2 * N; len += 2)
        for (int l = 0; l + len - 1 < 2 * N; l++) {
            int r = l + len - 1;
            // ③ 枚举 l 和谁配对
            for (int k = l + 1; k <= r; k += 2) {
                int cost = abs(A[l] - A[k]);
                int mid = (l + 1 <= k - 1) ? dp[l+1][k-1] : 0;
                int right = (k + 1 <= r) ? dp[k+1][r] : 0;
                dp[l][r] = min(dp[l][r], cost + mid + right);
            }
        }
    printf("%d\n", dp[0][2*N-1]);
}

逐行解析：

• ① 单个元素不可能被删除（每次删 2 个），但设为 0 作为递推基础。
• ② 区间长度只枚举偶数——奇数长度的区间不可能被全部删完。
• ③ $l$ 和 $k$ 配对，$k-l$ 为奇数。abs(A[l]-A[k]) 是配对代价，dp[l+1][k-1] 是中间部分删完的代价，dp[k+1][r] 是右边删完的代价。

模拟：$A = [6, 2, 3, 9, 8, 6]$（$N=3$）。

长度 2 的区间：$dp[0][1]=|6-2|=4$, $dp[1][2]=|2-3|=1$, $dp[2][3]=|3-9|=6$, $dp[3][4]=|9-8|=1$, $dp[4][5]=|8-6|=2$。

长度 4 的区间：

• $dp[0][3]$：$(0,1)$ 配+ $dp[2][3]=6$ → $4+6=10$；或 $(0,3)$ 配+ $dp[1][2]=1$ → $|6-9|+1=4$。取 4。
• $dp[1][4]$：$(1,2)$ 配+ $dp[3][4]=1$ → $1+1=2$；或 $(1,4)$ 配+ $dp[2][3]=6$ → $|2-8|+6=12$。取 2。
• $dp[2][5]$：$(2,3)$ 配+ $dp[4][5]=2$ → $6+2=8$；或 $(2,5)$ 配+ $dp[3][4]=1$ → $|3-6|+1=4$。取 4。

长度 6 的区间 $dp[0][5]$：

• $(0,1)$ 配+ $dp[2][5]=4$ → $4+4=8$
• $(0,3)$ 配+ $dp[1][2]+dp[4][5]=1+2=3$ → $|6-9|+3=6$
• $(0,5)$ 配+ $dp[1][4]=2$ → $|6-6|+2=\mathbf{2}$

答案 = 2。✓

---

例题 2：TB B21 — Longest Subpalindrome（最长回文子序列）

题目：长度 $N$ 的字符串 $S$，求最长回文子序列的长度。

数据范围：$1 \le N \le 1000$

—— AtCoder Tessoku Book B21

分析：教材 4.6 节的区间 DP。状态 $dp[l][r]$ = 子串 $S[l \ldots r]$ 中最长回文子序列长度。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[1009][1009];

int main() {
    int N;
    char S[1009];
    scanf("%d%s", &N, S);

    // ① 长度 1：单字符回文
    for (int i = 0; i < N; i++) dp[i][i] = 1;
    // ② 长度 2：相邻两字符
    for (int i = 0; i < N - 1; i++)
        dp[i][i+1] = (S[i] == S[i+1]) ? 2 : 1;

    // ③ 按区间长度递增
    for (int len = 2; len < N; len++)
        for (int l = 0; l + len < N; l++) {
            int r = l + len;
            if (S[l] == S[r])
                dp[l][r] = dp[l+1][r-1] + 2;        // ④ 两端匹配
            else
                dp[l][r] = max(dp[l+1][r], dp[l][r-1]); // ⑤ 去掉一端
        }
    printf("%d\n", dp[0][N-1]);
}

逐行解析：

• ①② 边界：单字符回文长 1，双字符看是否相同。
• ③ 区间 DP 的核心——按长度递增计算。
• ④ $S[l] = S[r]$ 时两端同时选入回文，中间部分的最优解来自 $dp[l+1][r-1]$。
• ⑤ 两端不同，至少有一端不选，取去掉左端或右端的较大值。

模拟：$S$ = “character”（$N=9$）。

len	关键更新
1	dp[i][i] = 1
2	dp[2][3]=‘ra’不匹配→1, dp[4][5]=‘cc’匹配→2
3	dp[0][2]=‘cha’→max(dp[1][2],dp[0][1])=1, dp[4][6]=‘cac’→dp[5][5]+2=3
…	…
8	dp[0][8] → 最长回文子序列 “caac” 或 “caaac” 等长度

最终 dp[0][8] = 5（如 “caaac”）。具体回文内容取决于字符串，但算法正确性不依赖具体还原。

---

例题 3：括号匹配——最少补几个括号

场景：给定长度 $N$ 的括号序列 $S$（只含 ( 和 )），求最少需要插入多少个括号才能使序列合法。

数据范围：$1 \le N \le 500$

分析：等价于求最长合法括号子序列。合法括号序列要求：(A)B 形式，其中 $A$ 和 $B$ 也是合法的。

状态：$dp[l][r]$ = 子串 $S[l \ldots r]$ 中最长合法括号子序列的长度。

转移：

• 如果 $S[l]$ 和 $S[r]$ 匹配（( 和 )），$dp[l][r] = dp[l+1][r-1] + 2$
• 枚举分割点：$dp[l][r] = \max_{k}(dp[l][k] + dp[k+1][r])$

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[509][509];

int main() {
    int N;
    char S[509];
    scanf("%d%s", &N, S);

    // ① 按区间长度递增
    for (int len = 2; len <= N; len++)
        for (int l = 0; l + len - 1 < N; l++) {
            int r = l + len - 1;
            // ② 如果两端匹配
            if (S[l] == '(' && S[r] == ')')
                dp[l][r] = dp[l+1][r-1] + 2;
            // ③ 枚举分割点
            for (int k = l; k < r; k++)
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r]);
        }
    // ④ 需要补充的括号数 = 总长度 - 最长合法子序列长度
    printf("%d\n", N - dp[0][N-1]);
}

逐行解析：

• ② 两端是 ( 和 ) 时可以配对，长度 +2。
• ③ 枚举分割点，取最优的切法。
• ④ 最长合法子序列不需要补充，其余每个字符需要补一个对应的括号。

---

例题 4：矩阵链乘法

场景：$N$ 个矩阵 $M_1, \ldots, M_N$，$M_i$ 的大小为 $R_{i-1} \times R_i$。求最少乘法次数。

数据范围：$1 \le N \le 500$

分析：经典的区间 DP。$dp[l][r]$ = 矩阵 $M_l \ldots M_r$ 连乘的最少乘法次数。

转移：$dp[l][r] = \min_{l \le k < r}(dp[l][k] + dp[k+1][r] + R_{l-1} \times R_k \times R_r)$。

最后合并时，左边结果是 $R_{l-1} \times R_k$ 的矩阵，右边是 $R_k \times R_r$ 的矩阵，乘法次数 $R_{l-1} \times R_k \times R_r$。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const long long INF = 1e18;
long long dp[509][509];
int R[509];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i <= N; i++) scanf("%d", &R[i]); // R[0]..R[N]

    for (int i = 1; i <= N; i++) dp[i][i] = 0;         // ① 单个矩阵不用乘
    for (int len = 2; len <= N; len++)
        for (int l = 1; l + len - 1 <= N; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r],
                    dp[l][k] + dp[k+1][r] + 1LL * R[l-1] * R[k] * R[r]); // ② 合并代价
        }
    printf("%lld\n", dp[1][N]);
}

逐行解析：

• ① 单个矩阵不需要乘法，代价 0。
• ② $M_l \ldots M_k$ 的结果是 $R_{l-1} \times R_k$，$M_{k+1} \ldots M_r$ 的结果是 $R_k \times R_r$，两者相乘需要 $R_{l-1} \times R_k \times R_r$ 次乘法。

模拟：$N=3$，矩阵大小 $10 \times 100$，$100 \times 5$，$5 \times 50$。$R = [10, 100, 5, 50]$。

$dp[1][2] = 10 \times 100 \times 5 = 5000$。 $dp[2][3] = 100 \times 5 \times 50 = 25000$。 $dp[1][3]$：

• $k=1$：$dp[1][1] + dp[2][3] + 10 \times 100 \times 50 = 0 + 25000 + 50000 = 75000$
• $k=2$：$dp[1][2] + dp[3][3] + 10 \times 5 \times 50 = 5000 + 0 + 2500 = \mathbf{7500}$

答案 = 7500。先算前两个再算最后一个更优。✓

参考文献

教材讲解 — 競技プログラミングの鉄則 第 4 章

• 4.6 B21 Longest Subpalindrome（区间 DP/回文子序列 解说）

系统练习 — 競技プログラミングの鉄則

• B21 Longest Subpalindrome（最长回文子序列）【例题】

实战练习 — 競プロ典型 90 問

• 019 Pick Two（★6，相邻配对删除 区间 DP）【例题】
• 088 Similar but Different Ways（★6，子集和重复判定）
• 089 Partitions and Inversions（★7，区间分割计数 逆序数）
• 090 Tenkei90’s Last Problem（★7，区间 min×len 条件计数）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化