区间 DP
区间 DP 是可以由小区间的结果往两边扩展一位得到大区间的结果，或者由两个小区间的结果可以拼出大区间的结果的一类 DP 问题
往往设 \(dp[i][j]\) 表示处理完 \([i,j]\) 区间得到的答案，按长度从小到大转移
因此一般是先写一层循环从小到大枚举长度 \(len\)，再写一层循环枚举左端点 \(i\)，算出右端点 \(j\)，然后写 \(dp[i][j]\) 的状态转移方程
区间 DP 也可以由大区间推到小区间，此时可以从大到小枚举 \(len\)
区间 DP 的提示信息：
- 从两端取出或在两端插入，这就是大区间变到小区间或者小区间变到大区间
- 合并相邻的，这样的一步相当于把已经处理好的两个小区间得到的结果合并为当前大区间的结果
- 消去连续一段使两边接起来，可以枚举最后一次消哪个区间，这样就可以把大区间拆成小区间
- 两个东西可以配对消掉，这时往往可以按左端点和哪个东西配对，把当前区间拆成两个子区间的问题
- 时间复杂度通常为 \(O(n^2)\) 或 \(O(n^3)\)
例：P2858 [USACO06FEB] Treats for the Cows G/S
解题思路
考虑操作过程，以第一步为例，你会把 \([1,n]\) 通过拿走最左边一个或最右边一个变为 \([2,n]\) 或 \([1,n-1]\)，这就是区间的变化
我们可以考虑最后一次拿零食，此时一定是只剩一件零食了，这就是长度为 \(1\) 的区间，由于它一定是最后一天出售，此时它的售价为 \(n*v[i]\)
由此我们设计 \(dp[i][j]\) 表示卖光 \([i,j]\) 区间内的零食的最大售价
那么状态转移方程就是 \(dp[i][j] = \max (dp[i+1][j] + v[i] * (n-(j-i)), dp[i][j-1]+v[j]*(n-(j-i)))\)
初始化 \(dp[i][i]=v[i]*n\)，从小区间往大区间推，最后答案为 \(dp[1][n]\)
时间复杂度 \(O(n^2)\)
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2005;
int v[N], dp[N][N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
dp[i][i] = v[i] * n;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1, a = n - len + 1;
dp[i][j] = max(dp[i + 1][j] + v[i] * a, dp[i][j - 1] + v[j] * a);
}
}
printf("%d\n", dp[1][n]);
return 0;
}
例：P3205 [HNOI2010] 合唱队
解题思路
每次插入到队伍最左边或最右边，也就是说如果 \([i,j]\) 排好了，接下来一个人插到左边就排好了 \([i-1,j]\) 区间，如果插到右边就排好了 \([i,j+1]\) 区间，这就是小区间推到大区间
但是能不能插进来还要看这次加入的数和上一次插入的数是否符合对应的大小关系，因此我们还需要知道插入的最后一个数是最左边的还是最右边的
可以设 \(dp_{i,j,0/1}\) 表示把 \([i,j]\) 区间排好且最后一个人是在左边/右边的方案数，初始化 \(dp_{i,i,0}=1\)，即只有一个人的时候强制认为它是插入在左边
考虑转移，对于 \(dp_{i,j,0}\)，此时就是看 \(h_i\) 插进来的时候能否符合题目中的条件，此时需要知道 \([i+1,j]\) 中最后插进来的是哪个，如果是 \(h_{i+1}\)，并且 \(h_i \lt h_{i+1}\)，那么 \(dp_{i,j,0}\) 加上 \(dp_{i+1,j,0}\)，如果是 \(h_j\)，并且 \(h_i \lt h_j\)，那么 \(dp_{i,j,0}\) 加上 \(dp_{i+1,j,1}\)
对于 \(dp_{i,j,1}\)，此时就是看 \(h_j\) 插进来的时候能否符合题目中的条件，此时需要知道 \([i,j-1]\) 中最后插进来的是哪个，如果是 \(h_i\)，并且 \(h_j \gt h_i\)，那么 \(dp_{i,j,1}\) 加上 \(dp_{i,j-1,0}\)，如果是 \(h_{j-1}\)，并且 \(h_j \gt h_{j-1}\)，那么 \(dp_{i,j,1}\) 加上 \(dp_{i,j-1,1}\)
时间复杂度 \(O(n^2)\)
参考代码
#include <cstdio>
const int N = 1005;
const int MOD = 19650827;
int dp[N][N][2], h[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i]);
dp[i][i][0] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
// [i,j] from [i+1,j] [i,j-1]
if (h[i] < h[i+1]) dp[i][j][0] = (dp[i][j][0] + dp[i+1][j][0]) % MOD;
if (h[i] < h[j]) dp[i][j][0] = (dp[i][j][0] + dp[i+1][j][1]) % MOD;
if (h[j] > h[i]) dp[i][j][1] = (dp[i][j][1] + dp[i][j-1][0]) % MOD;
if (h[j] > h[j-1]) dp[i][j][1] = (dp[i][j][1] + dp[i][j-1][1]) % MOD;
}
}
printf("%d\n", (dp[1][n][0] + dp[1][n][1]) % MOD);
return 0;
}
例：P3146 [USACO16OPEN] 248 G
这个问题和之前扩展一位的问题略有不同，这是由两个区间的结果合并推到更大区间的结果
解题思路
可以设 \(dp_{i,j}\) 表示把 \([i,j]\) 合并得到的最大数，如果这一段无法合并成一个数，则 \(dp\) 值为 \(0\)
初始化 \(dp_{i,i}=a_i\)
考虑转移，对于区间 \([i,j]\)，我们需要枚举分界点 \(k\)，将 \([i,j]\) 拆成 \([i,k]\) 和 \([k+1,j]\) 这两部分，先让 \([i,k]\) 合成一个数，\([k+1,j]\) 合成一个数，再让这两个数合并
这样就可以写出状态转移方程：如果 \(dp_{i,k}\) 和 \(dp_{k+1,j}\) 相等且非 \(0\)，则 \(dp_{i,j}= \max (dp_{i,j}, dp_{i,k}+1)\)，最后答案为 \(\max \{dp_{i,j}\}\)
时间复杂度 \(O(n^3)\)
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 250;
int dp[N][N];
int main()
{
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &dp[i][i]);
ans = max(ans, dp[i][i]);
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
if (dp[i][k] == dp[k + 1][j] && dp[i][k])
dp[i][j] = max(dp[i][j], dp[i][k] + 1);
ans = max(ans, dp[i][j]);
}
}
printf("%d\n", ans);
return 0;
}
例：P4170 [CQOI2007] 涂色
解题思路
考虑染色过程，因为是一段一段染的，长段可以看成是两个短段拼起来，并且如果某一次染了一段之后，可以在这段内部继续染色，这都提示我们可以考虑区间 DP
设 \(dp_{i,j}\) 表示染完 \(i\) 到 \(j\) 的最少次数，初始化 \(dp_{i,i}=1\)，一段拆成两段染，则有 \(dp_{i,j} = \min \{dp_{i,k}+dp_{k+1,j}\}\)
特殊情况：如果 \(s_i = s_j\)，可以在染完 \([i+1,j]\) 或 \([i,j-1]\) 的时候顺带把 \(i\) 或 \(j\) 染了，这样的结果一定优于拆两段，此时 \(dp_{i,j}= \min (dp_{i,j-1}, dp_{i+1,j})\)
分析：拆段意味着存在两步分别染 \([i,x_1]\) 和 \([x_2,j]\)，而不拆段则可以直接改成在第一步染一次 \([i,j]\)，染这一次也不会干扰到后续染色过程，因为后续染色是直接覆盖中间的某段区域，所以之前被这次 \([i,j]\) 染过也没有关系
对于其他题目，有可能出现在可以不拆段时依然是拆段取到最优解的情况，注意分析，如果想简化分析过程可以统一枚举拆段转移最优解的过程，因为在可能需要拆段的题目中这样做不会影响时间复杂度
时间复杂度 \(O(n^3)\)
参考代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
char s[N];
int dp[N][N];
int main()
{
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + (s[i] != s[j]);
for (int k = i; k < j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
printf("%d\n", dp[1][n]);
return 0;
}
例：CF607B Zuma
解题思路
设 \(dp_{i,j}\) 为移除 \([i,j]\) 的最短时间，则有初始化
\(\begin{cases} dp_{i,i}=1 & \\ dp_{i,i+1}=1 & c_i=c_{i+1} \\ dp_{i,i+1}=2 & c_i \ne c_{i+1} \end{cases}\)
状态转移方程
\(\begin{cases} dp_{i,j}=dp_{i+1,j-1} & c_i=c_j \\ dp_{i,j}=\min \{ dp_{i,k}+dp_{k+1,j} \} \end{cases}\)
注意：就算是 \(c_i=c_j\)，也有可能是拆段更优，比如 \([1, 2, 1, 1, 3, 1]\)
因此无论 \(c_i\) 是否等于 \(c_j\)，都必须做拆段的这种转移，时间复杂度 \(O(n^3)\)
环形 DP
有时我们会面临输入是环形数组的情况，即认为 \(a[n]\) 和 \(a[1]\) 是相邻的，此时应该如何处理？
-
如果是线性 DP，比如选数问题，可以对 \(a[n]\) 是否选进行分类，假设 \(a[n]\) 不选，把 \(dp[1][\dots]\) 初始化好，最后推到 \(dp[n][\dots]\) 时，只留下 \(a[n]\) 不选的情况计入答案；再假设 \(a[n]\) 选，把 \(dp[1][\dots]\) 初始化好，最后推到 \(dp[n][\dots]\) 时，只留下 \(a[n]\) 选的情况计入答案
-
如果是区间 DP，一种常见的方法是破环成链，将数组复制一倍接在原数组之后，然后对这个长度为 \(2n\) 的数组进行长度不超过 \(n\) 的区间 DP
\(dp[i][j]\) 中 \(i \le n\) 且 \(j>n\) 的情况就是把 \(a[n]\) 和 \(a[1]\) 也看成了相邻的，比如 \(dp[2][n+1]\)，就代表原数组 \(a[2],\dots,a[n],a[1]\) 这样一个环上的结果
例：P1880 [NOI1995] 石子合并
解题思路
破环成链后，对产生的长度为 \(2n\) 的数组中区间长度 \(\le n\) 的所有区间进行 DP
设 \(dpmax_{i,j}\) 表示将 \([i,j]\) 区间合并的最大得分，则有 \(dpmax_{i,j} = \max \{ dpmax_{i,k} + dpmax_{k+1,j} + (a_i + \dots + a_j) \}\)
设 \(dpmin_{i,j}\) 表示将 \([i,j]\) 区间合并的最小得分，则有 \(dpmin_{i,j} = \min \{ dpmin_{i,k} + dpmin_{k+1,j} + (a_i + \dots + a_j) \}\)
其中 \(a_i + \dots + a_j\) 可以利用前缀和预处理 \(O(1)\) 得到，总时间复杂度 \(O(n^3)\)，最后答案为 \(dpmax_{i,i+n-1}\) 中的最大值和 \(dpmin_{i,i+n-1}\) 中的最小值
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 205;
const int INF = 1e9;
int a[N], sum[N];
int dp1[N][N];
int dp2[N][N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
a[i + n] = a[i];
}
for (int i = n + 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i];
for (int i = 1; i < 2 * n; i++)
for (int j = 1; j < 2 * n; j++) {
dp1[i][j] = INF;
dp2[i][j] = 0;
}
for (int i = 1; i < 2 * n; i++) dp1[i][i] = 0;
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= 2 * n - len; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + sum[j] - sum[i - 1]);
dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]);
}
}
}
int ans1 = INF, ans2 = 0;
for (int i = 1; i <= n; i++) {
ans1 = min(ans1, dp1[i][i + n - 1]);
ans2 = max(ans2, dp2[i][i + n - 1]);
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
例：P1063 [NOIP2006 提高组] 能量项链
解题思路
与石子合并基本相同，先破环成链，然后设 \(dp_{i,j}\) 表示把 \([i,j]\) 的能量珠合成一个时释放的最大总能量
则有 \(dp_{i,j} = \max \{ dp_{i,k} + dp_{k+1,j} + a_i * a_{k+1} * a_{j+1} \}\)
需要注意要乘的三个数是哪三个，尤其是最后一个数，因为需要 \(a_{j+1}\)，所以可以在刚开始复制 \(a\) 数组时多复制一位，让 \(a_{2*n+1}\) 也等于 \(a_1\)
最后答案为 \(\max \{ dp_{i,i+n-1} \}\)，时间复杂度 \(O(n^3)\)
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 205;
int a[N], dp[N][N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
}
a[2 * n + 1] = a[1];
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= 2 * n - len; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, dp[i][i + n - 1]);
printf("%d\n", ans);
return 0;
}