区间型动态规划，即区间 DP，主要用于解决涉及区间的问题。换句话说，这类 DP 问题总是从小的区间转移到大的区间，以区间为子问题。
怎么做？
例题 \(1:\) P1775 石子合并。
观察题目，我们可以发现，不管前面的石子是怎么合并的，最终都是仅剩的两堆石子合并在一起。对于一段需要合并成一堆的石子区间 \([i,j]\)，总是可以找到一个分界点 \(k(i\le k<j)\)，让 \([i,k]\) 和 \([k+1,j]\) 分别先合并成两堆石子，再将这两堆石子合并，使得区间 \([i,k]\) 合并的代价 \(+\) 区间 \([k+1,j]\) 合并的代价 \(+\) \([i,k]\) 合并的一堆石子和 \([k+1,j]\) 合并的一堆石子合并的代价 \(=[i,j]\) 合并的代价（有点绕），而我们要做的，就是枚举并找到最优的 \(k\)。
直接定义状态 \(dp_{i,j}\) 为将区间 \([i,j]\) 合并的最小代价，则有：
\[dp_{i,j}=\min_{k=i}^{j-1}dp_{i,k}+dp_{k+1,j}+合并的代价 \]（这样或许好懂一些）
在这里，我们就将小区间的值转移给了大区间，完成了转移。至于合并的代价，将 \([i,j]\) 内的石子全部合并必然意味着所有石子的数量都会相加，就可以用前缀和 \(sum_i-sum_{j-1}\) 来计算。
完整的状态转移方程：
\[dp_{i,j}=\min_{k=i}^{j-1}dp_{i,k}+dp_{k+1,j}+sum_i-sum_{j-1} \]还有一点，就是 DP 中的初始状态。由于一堆石子（\(dp_{i,i}\)）已经是一堆了，所以不需要进行任何操作，代价也自然为 \(0\)。由于要取最小值，其余则设为极大值。
答案自然为 \(dp_{1,n}\)（整个区间）。
区间 DP 就是这样。状态的设计一般至少有两维，即 \(dp_{i,j}\)，代表区间的起点和终点。那么，我们该怎么枚举区间并从小到大转移呢？很简单，我们先枚举区间长度 \(len\)，从 \(2\) 到 \(n\)，这样就保证了区间是从小到大的（区间长度为 \(1\) 的是初始情况）。接着，我们再从 \(1\) 开始枚举起点 \(i\)，但是需要保证区间合法，即 \(i+len-1\le n\)。有了区间长度和起点，自然也可以求出终点 \(j=i+len-1\)。接着，再枚举 \(k\) 转移就行啦！
常见的区间 DP 状态：\(dp_{i,j}\) 表示区间 \([i,j]\) 的 XXX 的最大值、最小值、方案数。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n, a[N], dp[N][N], s[N];
int main() {
cin >> n;
memset(dp, 0x3f, sizeof dp); // 求最小值设极大值
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[i][i] = 0; // 初始状态
s[i] = s[i - 1] + a[i]; // 前缀和优化
}
for (int len = 2; len <= n; len++) { // 区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 起点
int j = i + len - 1;
for (int k = i; k <= j - 1; k++) // 枚举 k
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); // 转移
}
}
cout << dp[1][n]; // 答案
return 0;
}
例题 \(2:\) P3146 248 G。
又是合并数字，只不过这次要求的东西不一样，那么状态也就自然要进行一些改变了。
\(1.\) 状态：\(dp_{i,j}\) 表示区间 \([i,j]\) 的数字合并后的最大值。
\(2.\) 转移：像石子合并一样，考虑枚举中间点 \(k\)。这时候有一个问题：通过样例，我们发现对于某个区间 \([i,j]\)，是有可能不会全部合成只剩一个数的。比方说答案的整个区间 \([1,n]\)，我们在样例中发现，我们只是将后 \(3\) 个数，也就是区间 \([2,n]\) 合并成了 \(3\)，而第一个数根本没动过。也就是说，我们如果要将 \(dp_{i,k}\) 和 \(dp_{k+1,j}\) 合并，还得保证这两个区间合并后的最大值相邻才能合并，但这显然很麻烦，不可行。
但是观察到，真正合并成一个数的一定是一个完整的区间，比如样例的 \([2,n]\)，而不一定是不能合成只有一个数的区间 \([1,n]\)。不如给状态加上约束：\(dp_{i,j}\) 表示区间 \([i,j]\) 的数字合并成一个数后的最大值。这样，答案便不是 \(dp_{1,n}\) 了，而是 \(\max(dp_{i,j})\)，因为区间 \([1,n]\) 不一定能合并成一个数。
这样，保证了区间合并后只会剩一个数字，转移也就很轻松了：
\[dp_{i,j}=\max(dp_{i,j},dp_{i,k}+1),dp_{i,k}=dp_{k+1,j} \]\(3.\) 初始状态：区间长度为 \(1\) 的 \(dp_{i,i}\) 是最小的子问题，而一个数显然无法进行任何操作，故 \(dp_{i,i}=a_i\)。
248 G 区间 DP 代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 250;
int n, a[N], dp[N][N], ans = -1e9;
int main() {
cin >> n;
memset(dp, -0x3f, sizeof dp);
for (int i = 1; i <= n; i++)
cin >> a[i], dp[i][i] = a[i], ans = max(ans, a[i]);
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
if (dp[i][k] == dp[k + 1][j])
dp[i][j] = max(dp[i][j], dp[i][k] + 1);
ans = max(ans, dp[i][j]);
}
}
cout << ans;
return 0;
}
通过这两道例题，我们可以发现：区间 DP 的转移是没有固定顺序的，而且总是在做合并。
那这时就有人问了：P1090 合并果子也是合并，为什么却是贪心呢？答案是，因为合并果子是任取两堆果子合并，而合并石子，248 G 都是合并相邻的数，有限制，并不是只用贪心就能获得最优解的，所以我们要用区间 DP。
例题 \(3:\) P1622 释放囚犯。
明明不是合并，却是区间 DP。 —— Weekoder
感觉很像区间 DP，但又不知道怎么写。这时候，我们就要运用逆向思维：把释放囚犯看做抓囚犯，每抓一个囚犯，他旁边的囚犯就都要发肉。初始时，囚犯一共有 \(Q+1\) 段。在发肉时，不会给抓进来的囚犯发肉，但在后面会给他发肉。抛开这一点不谈，这不就变成了一个石子合并了吗？
第一部分：初始化。我们定义 \(num_i\) 为第 \(i\) 段囚犯的人数，即石子的数量。我们有 \(num_i=a_i-a_{i-1}-1\)。这是怎么推出来的呢？一个区间内的人数 \(a_i-a_{i-1}+1\) 再减去两端要被抓进来的囚犯 \(a_i-a_{i-1}+1-2=a_i-a_{i-1}-1\)。由于区间有 \(Q+1\) 段，我们可以虚拟一个点 \(a_{Q+1}=p+1\)。像石子合并一样，我们还要求出 \(num\) 的前缀和 \(sum\)。别忘了初始化 \(dp_{i,i}=0\)。
第二部分：DP。还是和石子合并一样的枚举 \(len\) 和 \(i\)，不过这次的范围是 \(Q\)。注意，此时因为虚拟了最后一个点，\(Q\) 已经变为了 \(Q+1\)。在石子合并的状态转移方程的基础上，我们还要考虑被抓进去的囚犯后面还是要计算的点，那这样的囚犯有多少个呢？从 \(i\) 合并到 \(j\)，模拟一下就会发现有 \(j-i\) 个已经被抓进去的囚犯要发肉，减掉这次抓的囚犯不会发的肉，答案即为 \(j-i-1\)。状态转移方程：
\[dp_{i,j}=\min(dp_{i,j},dp_{i,k}+dp_{k+1,j}+sum_j-sum_{i-1}+j-i-1) \]下面给出代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int p, q, a[N], dp[N][N], num[N], sum[N];
int main() {
cin >> p >> q;
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= q; i++)
cin >> a[i];
a[++q] = p + 1;
for (int i = 1; i <= q; i++)
num[i] = a[i] - a[i - 1] - 1, sum[i] = sum[i - 1] + num[i], dp[i][i] = 0;
for (int len = 2; len <= q; len++) {
for (int i = 1; i + len - 1 <= q; i++) {
int j = i + len - 1;
for (int k = i; k <= j - 1; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
dp[i][j] += sum[j] - sum[i - 1] + j - i - 1;
}
}
cout << dp[1][q];
return 0;
}
例题 \(3:\) P4170 [CQOI2007] 涂色。
这道题也是一个很明显的区间 DP：每次涂色的区域都是区间，而且没有固定的涂色顺序。
依然设计状态 \(dp_{i,j}\) 表示将区间 \([i,j]\) 涂色至目标颜色的最短涂色次数。显然，初始状态为 \(dp_{i,i}=1\)，也就是一格直接涂色即可。
考虑转移。这时候，就出现不一样的东西了：分类讨论。首先考虑对于一个区间 \([i,j]\)，如果 \(s_i=s_j\)，该如何转移？既然 \(s_i=s_j\)，那就代表我可以在涂 \(s_j\) 的时候顺便把 \(s_i\) 也涂了，那么花费就相当于是 \(dp_{i+1,j}\)。反过来想，我也可以在涂 \(s_i\) 的时候顺便把 \(s_j\) 涂了，那么花费就是 \(dp_{i,j-1}\)。两者取较小值即可。
可能这个时候就会有爱思考的同学说了：既然 \(s_i=s_j\)，那么为什么不能在涂区间 \([i,j]\) 的时候先全部涂 \(s_i(s_j)\) 的颜色，然后再涂 \([i+1,j-1]\)，也就是 \(dp_{i+1,j-1}+1\) 呢？我尝试后发现，这样只能拿 \(50\) 分，因为这并不是最优的。可以这样考虑：在 \([i+1,j-1]\) 中有一个 \(s_k\)，它等于 \(s_i\) 或者 \(s_j\)。此时 \(s_i=s_j\)，在 \([i+1,j-1]\) 内又有一个 \(s_k=s_i=s_j\)，那为什么不能直接将 \(s_i\) 和 \(s_j\) 在涂 \(s_k\) 的时候一起顺便涂了呢？所以，这个时候就不需要将 \(dp_{i+1,j-1}+1\)，答案可直接取 \(dp_{i+1,j-1}\)。我又尝试了枚举这个 \(s_k\)，但还是只得了 \(60\) 分。综合以上所述，\(\min(dp_{i+1,j},dp_{i,j-1})\) 考虑的更全面，状态更优。
接着，就是另一种情况：\(s_i\ne s_j\)。根据刚刚的思路，我们可以发现，\(s_i\) 和 \(s_j\) 是整个区间的“底色”。于是，我们只需要枚举断点 \(k(i\le k<j)\)，\([i,k]\) 内的底色为 \(s_i\)，\([k+1,j]\) 内的底色为 \(s_j\)。状态转移方程为 \(dp_{i,j}=\min(dp_{i,k}+dp_{k+1,j})\)。
这还有一个技巧，就是字符串的下标是从 \(0\) 开始的。如何让下标从 \(1\) 开始呢？其实，我们只需要在字符串前面补一个字符就行了，即 s = '#' + s。
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
string s;
int n, dp[N][N];
int main() {
cin >> s;
n = s.size();
s = '#' + s;
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (s[i] == s[j]) dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]);
else {
for (int k = i; k <= j - 1; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
cout << dp[1][n];
return 0;
}
区间 DP 的特征
好了，做了这些题目，我们是时候该总结一下区间 DP 的一些套路和特征了。从上面这些例题中，可以发现：
- 从左往右，从右往左递推会得到不同的结果；
- 区间 DP 通常是合并类问题或者拆分类问题，或者处理两端类问题；
- 状态转移要么是枚举中间断点，要么是枚举 \(2\) 个端点。
接下来，让我们继续来看一道处理两端的问题。
例题 \(4:\) P2858 [USACO06FEB] Treats for the Cows G/S。
由于每次只能拿两端的零食，很符合处理两段类问题，考虑区间 DP。
定义 \(dp_{i,j}\) 为将区间 \([i,j]\) 外所有零食都拿走的前提下区间 \([i,j]\) 能产生的最大价值。那么，答案显然为 \(dp_{1,n}\)。
初始状态是什么？\(dp_{i,i}\) 表示其他零食都拿完了，只剩第 \(i\) 个零食了，那么当时肯定是最后一天，第 \(n\) 天。显然，产生的价值为 \(a_i\times n\)。
既然是两端类问题，那么状态肯定也只能从 \([i+1,j]\) 或 \([i,j-1]\) 转移而来。其实很简单：要么拿零食 \(i\)，要么拿零食 \(j\)。前者的价值为 \(a_i\times 当前天数+dp_{i+1,j}\)，后者的价值为 \(a_j\times 当前天数+dp_{i,j-1}\)。重点是，如何求出当前天数？一共有 \(n\) 天，剩下的还有当前区间的长度 \(len=j-i+1\) 天，算一下容易得到当前天数为 \(n-len+1\)。记 \(days=n-len+1\)，状态转移方程为：
\[dp_{i,j}=\max(dp_{i+1,j}+a_i\times days,dp_{i,j-1}+a_j\times days) \]代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, a[N], dp[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], dp[i][i] = a[i] * n;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1, days = n - len + 1;
dp[i][j] = max(dp[i + 1][j] + a[i] * days, dp[i][j - 1] + a[j] * days);
}
}
cout << dp[1][n];
return 0;
}
例题 \(5:\) P2890 [USACO07OPEN] Cheapest Palindrome G。
首先看到题目，这是一道区间 DP 吗？是的，因为我可以通过操作来从小的回文串变为大的回文串。如果是这样，那我们必须要意识到一点：删除一个字符等同于在相对位置添加一个字符。既然是这样，那么我们只需要在两种操作的代价中取较小值即可，即为 \(val_i\)。
第一步，初始状态是什么？一个字符本身就是回文串，我们显然有 \(dp_{i,i}=0\)。
第二步，怎么转移？还是分类讨论：如果 \(s_i=s_j\)，那么 \(i,j\) 这一对位置本身就是回文的了，与涂色不同，我们只需要让 \([i+1,j-1]\) 回文即可，\(dp_{i,j}=\min(dp_{i,j},dp_{i+1,j-1})\)。但还要考虑越界的情况，即当 \(len=2\) 时，区间 \([i+1,j-1]\) 是不合法的，\(dp_{i,j}\) 直接等于 \(0\)。
如果 \(s_i\ne s_j\)，又该如何转移呢？肯定不是枚举断点，因为这和回文串没有关系，两段回文串拼在一起不一定是一个回文串。考虑两端转移。如果我已经让 \(dp_{i,j-1}\) 回文了，那 \(j\) 怎么办？要么删掉它，要么在对面补一个，我们肯定选择代价较小的 \(val_{s_j}\)。那么就是 \(dp_{i,j-1}+val_{s_j}\)。反过来，另一个端点就是 \(dp_{i+1,j}+val_{s_i}\)，两者取较小值即可。完整的状态转移方程：
\[dp_{i,j}=\min(dp_{i,j},dp_{i+1,j-1}),(s_i=s_j,len>2) \\ dp_{i,j}=0,(s_i=s_j,len=2) \\ dp_{i,j}=\min(dp_{i+1,j}+val_{s_i},dp_{i,j-1}+val_{s_j}),(s_i\ne s_j) \]代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, m, dp[N][N], val[130];
string s;
int main() {
memset(dp, 0x3f, sizeof dp);
cin >> n >> m >> s;
s = '#' + s;
for (int i = 1; i <= n; i++) {
char ch;
int x, y;
cin >> ch >> x >> y;
val[ch] = min(x, y);
}
for (int i = 1; i <= m; i++) dp[i][i] = 0;
for (int len = 2; len <= m; len++) {
for (int i = 1; i + len - 1 <= m; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
if (len == 2) dp[i][j] = 0;
else dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
}
else
dp[i][j] = min(dp[i + 1][j] + val[s[i]], dp[i][j - 1] + val[s[j]]);
}
}
cout << dp[1][m];
return 0;
}
例题 \(6:\) P1435 [IOI2000] 回文字串。
与上一道题几乎一样，只是代价变为了 \(1\)，少了一些理解上的困难（就因为这个，从蓝题变成了黄题）。这里就不提供代码了，供读者练习。
还有一点要注意的是，我们一般会用 \(n\) 来代表字符串的长度，即 n = s.size()，方便写区间 DP。但是我们还有一个操作 s = '#' + s，让字符串的下标从 \(1\) 开始。\(n\) 的赋值一定要写在修改 \(s\) 的前面，不然 \(n\) 就会多 \(1\)，导致我复制的上一题的代码都调了 10 分钟。
例题 \(7:\) P4302 [SCOI2003] 字符串折叠。
首先，这道题为什么是一个区间 DP 呢？很明显，我们折叠的顺序是不固定的，而且可以把折叠看做一次合并。
定义状态 \(dp_{i,j}\) 表示将区间 \([i,j]\) 折叠后的最短长度。一个字符不需要折叠，我们有初始状态 \(dp_{i,i}=1\)。
如何转移？我们可以先按常规的思路来：枚举断点，折叠后的字符串是可以拼在一起的，\(dp_{i,j}=\min(dp_{i,j},dp_{i,k}+dp_{k+1,j})\)。
然后，我们再考虑折叠。枚举 \(k\) 表示以 \([i,k]\) 为周期进行折叠。首先要判断，如果区间长度 \(len\) 不是折叠长度 \(k-i+1\) 的倍数，则不能折叠，直接跳过。然后，我们还需要检查整个区间 \([i,j]\) 的字符串是否以 \([i,k]\) 的字符串为周期，才能折叠。这里写一个判断函数即可。若可以折叠，则状态转移。
折叠后的字符串分为 \(3\) 部分：
- 两个括号；
- 折叠的数字；
- 折叠的字符串；
两个括号的长度明显为 \(2\)。折叠的数字为 \(len\div(k-i+1)\)，可以写一个函数返回数字的长度。折叠的字符串长度不能直接取 \(k-i+1\)，考虑到折叠嵌套的情况，应取 \(dp_{i,k}\)。总结一下，状态转移方程为：
\[dp_{i,j}=\min(dp_{i,j},dp_{i,k}+2+\operatorname{getlen}(len\div(k-i+1))) \]答案即为 \(dp_{1,n}\)。
下面给出完整代码，请参考代码自行理解：
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, dp[N][N];
string s;
bool check(int l, int r, int len) {
string tmp = s.substr(l, len);
for (int i = l; i + len - 1 <= r; i += len)
if (tmp != s.substr(i, len))
return 0;
return 1;
}
int getlen(int x) {
string tmp = to_string(x);
return tmp.size();
}
int main() {
memset(dp, 0x3f, sizeof dp);
cin >> s;
n = s.size();
s = '#' + s;
for (int i = 1; i <= n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
for (int k = i; k <= j; k++) {
int l = k - i + 1;
if (len % l) continue;
if (check(i, j, l))
dp[i][j] = min(dp[i][j], dp[i][k] + 2 + getlen(len / l));
}
}
}
cout << dp[1][n];
return 0;
}
例题 \(7:\) P4290 [HAOI2008] 玩具取名。
字符串由短扩展到长，可以视为按长度划分子问题，考虑区间 DP；
定义 \(dp_{i,j,0/1/2/3}\) 表示区间 \([i,j]\) 是否能通过 \(\texttt{W,I,N,G}\) 变换而来。还可以定义 \(yes_{c,c1,c2}\) 表示字符 \(c\) 是否可以用 \(c1,c2\) 组合而来。那么状态转移方程就可以枚举 \(c,c1,c2\)，如果 \([i,k]\) 能变为 \(c1\) 且 \([k+1,j]\) 能变为 \(c2\)，而且 \(c1\) 和 \(c2\) 能变为 \(c\)，那 \(dp_{i,j,c}=\text{True}\)。最后输出即可，还是有点难度的。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int a[4], num[130], n;
bool yes[4][4][4], dp[N][N][4];
string s, tmp = "WING";
int main() {
cin >> a[0] >> a[1] >> a[2] >> a[3];
num['W'] = 0, num['I'] = 1, num['N'] = 2, num['G'] = 3;
for (int c = 0; c < 4; c++) {
for (int i = 1; i <= a[c]; i++) {
char c1, c2;
cin >> c1 >> c2;
yes[c][num[c1]][num[c2]] = 1;
}
}
cin >> s;
n = s.size();
s = '#' + s;
for (int i = 1; i <= n; i++) dp[i][i][num[s[i]]] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++)
for (int c = 0; c < 4; c++)
for (int c1 = 0; c1 < 4; c1++)
for (int c2 = 0; c2 < 4; c2++)
dp[i][j][c] |= dp[i][k][c1] && dp[k + 1][j][c2] && yes[c][c1][c2];
}
}
bool flag = 1;
for (int c = 0; c < 4; c++)
if (dp[1][n][c])
cout << tmp[c], flag = 0;
if (flag) cout << "The name is wrong!";
return 0;
}
例题 \(8:\) P1220 关路灯。
可以发现，关灯的路灯总是一个区间，而且正在不断扩大，考虑区间 DP。而且只设计 \(dp_{i,j}\) 不太够，因为老张一定在关灯的路灯的两个端点，还得知道是从哪里来的：设 \(dp_{i,j,0/1}\) 表示将区间 \([i,j]\) 的灯关闭并且老张最后站在 \(i\) 或 \(j\) 的最小电量。有状态转移方程：
\(dp_{i,j,0}=\min(dp_{i+1,j,1}+(w_j-w_i)\times(sum_n-sum_j+sum_i),dp_{i+1,j,0}+(w_{i+1}-w_i)\times(sum_n-sum_j+sum_i))\)
\(dp_{i,j,1}\) 以此类推。
此题难度较大！！
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, c, dp[N][N][2], w[N], a[N], sum[N];
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> w[i] >> a[i], sum[i] = sum[i - 1] + a[i];
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++)
dp[i][i][0] = dp[i][i][1] = abs(w[c] - w[i]) * (sum[n] - a[c]);
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j][0] = min(dp[i + 1][j][1] + (w[j] - w[i]) * (sum[n] - sum[j] + sum[i]), dp[i + 1][j][0] + (w[i + 1] - w[i]) * (sum[n] - sum[j] + sum[i]));
dp[i][j][1] = min(dp[i][j - 1][1] + (w[j] - w[j - 1]) * (sum[n] - sum[j - 1] + sum[i - 1]), dp[i][j - 1][0] + (w[j] - w[i]) * (sum[n] - sum[j - 1] + sum[i - 1]));
}
}
cout << min(dp[1][n][0], dp[1][n][1]);
return 0;
}
例题 \(9:\) CF1114D Flood Fill。
可以先预处理，将颜色相同的区间合并成一个，就可以进行较为简单的区间 DP 了。
根据前面的经验，相信读者不难推出状态转移方程：
\[dp_{i,j}=0(i=j\text{ or }(a_i=a_j\text{ and }j-i+1=2))\\ dp_{i,j}=\min(dp_{i,j},dp_{i+1,j-1}+1)(a_i=a_j)\\ dp_{i,j}=\min(dp_{i+1,j}+1,dp_{i,j-1}+1)(a_i\ne a_j) \]轻松 A 掉此题。（）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int len, n, a[N], dp[N][N];
int main() {
memset(dp, 0x3f, sizeof dp);
cin >> len;
for (int i = 1; i <= len; i++)
cin >> a[i];
int n = unique(a + 1, a + 1 + len) - a - 1;
for (int i = 1; i <= n; i++) dp[i][i] = 0;
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (a[i] == a[j]) {
if (len == 2) dp[i][j] = 0;
else dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 1);
}
else
dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
}
}
cout << dp[1][n];
return 0;
}
结语
这应该算是一本习题册了吧，里面包含了 \(9\) 道区间 DP 的题目，有基础的模板题，也有困难的挑战思维题。可能不会讲解的特别详细，毕竟是习题册，还请谅解。