区间 DP，其实和普通的 DP 差不多。但是和普通 DP 不一样的是，它以一个区间的长度为阶段。一开始，我们知道长度为 \(1\) 的区间的值（即元区间，当然也可能知道长度 \(> 1\) 的某些区间的值），而我们就可以通过这些元区间来推出更长的区间的值，最后得到整个区间的值。
一般来讲，我们会定义状态 \(f_{i, j}\) 来表示下标为 \(i \sim j\) 的元素（即区间 \([i, j]\)）。
PS：假如是习题说明我懒得写 TJ 了，以后再写。
原题目链接：Link。
首先，我们定义 \(f_{i, j}\) 表示把下标为 \(i \sim j\) 的石子合并成一堆石子的代价。显然，一堆石子不需要合并，所以 \(f_{i, i} = 0\)。
因为每次只能选相邻的 \(2\) 堆石子合并成新的一堆，我们于是可以枚举一个中间点 \(k\)，从 \(k\) 分开成左右两堆，并把这两堆石子合并，代价是把这两堆石子分别合并的代价加上两堆石子数之和。于是有状态转移方程 \(f_{i, j} = \max\{f_{i, k} + f_{k + 1, j} + \sum_{l = i} ^ j a_l\} (i \leq k < j)\)。而 \(\sum_{l = i} ^ j a_l\) 可以使用前缀和 \(O(n)\) 处理后 \(O(1)\) 计算。
可以发现 \([i, j]\) 是由 \([i, k]\) 和 \([k + 1, j]\) 转移过来的，因此可以把区间长度 \(len\) 作为 DP 阶段，然后再枚举左端点 \(i\)，算出右端点 \(j = i + len - 1\)，然后枚举 \(k\) 来 DP。实际上，区间 DP 大都会进行这样的操作，先枚举 \(len\)，再枚举 \(i\)。
此算法时间复杂度为 \(O(n ^ 3)\)，代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n, a[N], f[N][N], s[N];
int main() {
memset(f, 0x3f, sizeof(f));
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i] /*,f[i][i] = 0*/, s[i] = s[i - 1] + a[i]; // 前缀和
for (int len = 2; len <= n; len++)
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n] << endl;
return 0;
}
原题目链接：Link。
我们可以发现，这道题和上一题差不多，除了——变成了一个环（圆形操场）。
这里，我们要搬出一个常用技巧了！在处理环形区间 DP 时，我们可以破环为链。具体的处理方法是，将这条链延长两倍，变成 \(2 \times n\) 堆石子，其中第 \(i\) 堆与第 \(i + n\) 堆相等。然后 DP 处理这条长为 \(2 \times n\) 的链，最后取 \(\max\{f_{i, i + n - 1}\}(1 \leq i \leq n)\) 即可（可以画图想一下）。处理最小值类似。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 405;
int n, a[N], f[N][N], s[N], dp[N][N];
int main() {
memset(f, 0x3f, sizeof(f));
memset(dp, 0xcf, sizeof(dp)); // 0x3f 极大值，0xcf 极小值
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], f[i][i] = dp[i][i] = 0, s[i] = s[i - 1] + a[i]; // 破环为链
for (int i = n + 1; i <= n << 1; i++)
a[i] = a[i - n], f[i][i] = dp[i][i] = 0, s[i] = s[i - 1] + a[i];
for (int len = 2; len <= n << 1; len++) // 记得 n * 2
for (int l = 1; l <= (n << 1) - len + 1; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++) {
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
}
}
int ans1 = INT_MAX, ans2 = 0;
for (int i = 1; i <= n; i++)
ans1 = min(ans1, f[i][i + n - 1]), ans2 = max(ans2, dp[i][i + n - 1]);
cout << ans1 << endl << ans2 << endl;
return 0;
}
原题目链接：Link。
（假设西瓜从 \(1 \sim n\) 编号。）
显然是区间 DP。我们可以设 \(f_{i, j}\) 为戳破区间 \([i, j]\) 的西瓜所能获得硬币的最大数量。
这里是番外。
翻看了网上大部分题解，发现基本都是设 \(f_{i, j}\) 为戳破区间 \((i, j)\) 的西瓜所能获得硬币的最大数量。但其实，包含 \(i\) 和 \(j\) 也是可以的。
怎么转移呢？
如果我们枚举第 \(1\) 个戳破的西瓜 \(k\)，那么我们无法准确地获取到这个西瓜左右两边的西瓜（因为可能 \(k - 1\) 或者 \(k + 1\) 个西瓜已经被戳过了），无法转移。
所以，我们枚举最后一个戳破的西瓜 \(k\)。在戳破西瓜 \(k\) 前，区间 \([i, k - 1]\) 和 \([k + 1, j]\) 的西瓜都已经被戳破了（这一部分即 \(f_{i, k - 1} + f_{k + 1, j}\)），那么西瓜 \(k\) 左边的就是西瓜 \(i - 1\)，右边的就是西瓜 \(j + 1\)，乘起来就是 \(nums_{i - 1} \times nums_{k} \times nums_{j + 1}\)。得到状态转移方程：
\[f_{i, j} = \max\{f_{i, k - 1} + f_{k + 1, j} + nums_{i - 1} \times nums_{k} \times nums_{j + 1}\} (i \leq k \leq j) \]注意这里可以取 \(i, j\)，因为是符合实际意义的（虽然 \(f_{i, i - 1}\) 或者 \(f_{j + 1, j}\) 看起来很反人类）！
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, a[N], f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = a[n + 1] = 1; // 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的西瓜，所以并不能被戳破。
for (int i = 1; i <= n; i++)
f[i][i] = a[i - 1] * a[i] * a[i + 1]; // 初始化元区间
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++)
f[i][j] = max(f[i][j], f[i][k - 1] + f[k + 1][j] + a[i - 1] * a[k] * a[j + 1]);
}
cout << f[1][n] << endl;
return 0;
}
当然，我们也可以设 \(f_{i, j}\) 为戳破区间 \((i, j)\) 的西瓜所能获得硬币的最大数量。
枚举最后一个戳破的西瓜 \(k\)，在戳破西瓜 \(k\) 前，区间 \((i, k - 1]\)（也就是 \([i, k)\)）和 \([k + 1, j)\)（也就是 \((k, j)\)）的西瓜都已经被戳破了（这一部分即 \(f_{i, k} + f_{k, j}\)），那么西瓜 \(k\) 左边的就是西瓜 \(i\)，右边的就是西瓜 \(j\)，乘起来就是 \(nums_{i} \times nums_{k} \times nums_{j}\)。得到状态转移方程：
\[f_{i, j} = \max\{f_{i, k} + f_{k, j} + nums_{i} \times nums_{k} \times nums_{j}\} (i < k < j) \]最后输出 \(f_{0, n + 1}\) 即可。注意这里我们定义的就是闭区间，所以 \(k\) 不能取 \(i, j\)。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, a[N], f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = a[n + 1] = 1;
for (int i = 1; i <= n; i++)
f[i][i] = a[i - 1] * a[i] * a[i + 1];
for (int len = 2; len <= n + 2; len++) // 计算 0 ~ n + 1，长度为 n + 2，所以 len 循环到 n + 2
for (int i = 0; i <= n - len + 2; i++) { // 同理，这里 i 的上界限制右端点，所以可以循环到 (n + 1) - len + 1
int j = i + len - 1;
for (int k = i + 1; k < j; k++)
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
}
cout << f[0][n + 1] << endl;
return 0;
}
有兴趣可以做一下 乘法拼图，几乎和上面的代码一样。
「习题」能量项链原题目链接：Link。
提示：破环为链，搞清头尾标记。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N], f[N][N], s[N], dp[N][N];
int main() {
s[0] = 1;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = n + 1; i <= n << 1; i++) a[i] = a[i - n];
for (int len = 2; len <= n; len++)
for (int l = 1; l <= (n << 1) - len + 1; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++)
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + a[l] * a[k + 1] * a[r + 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;
}
原题目链接：Link。
注意到题目求的是最长回文子串，而非最长回文子序列。子串是连续的，这一点要注意！
设 \(f_{i, j}\) 表示下标为 \(i \sim j\) 的字符串中的最长回文子串。容易想到根据 \(s_i\) 和 \(s_j\) 来转移。
如果 \(s_i = s_j\)，两端是回文的，我们就判断 \(f_{i + 1, j - 1}\) 是否等于 \((j - 1) - (i + 1) + 1 = j - i - 1\)。如果相等，说明中间整个都是回文的，然后再算上相等的两端，有 \(f_{i, j} = f_{i + 1. j - 1} + 2\)；如果不等，说明中间不整个都是回文，这时候我们不能直接拼上两端（否则不连续），只好忍痛割爱直接舍掉两端，有 \(f_{i, j} = f_{i + 1, j - 1}\)。
而在任何时候，我们都可以舍掉 \(i\) 或者 \(j\) 来转移，也就是 \(i, j\) 中一定有一个没用（都有用就是上面的 \(f_{i, j} = f_{i + 1. j - 1} + 2\))，有 \(f_{i, j} = \max(f_{i + 1, j}, f_{i, j - 1})\)。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5;
char s[N];
int f[N][N], n;
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++) f[i][i] = 1; // 记得初始化
for (int len = 2; len <= n; len++)
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
f[l][r] = max(f[l + 1][r], f[l][r - 1]); // 不仅是 s[l] != s[r] 的时候可以这么转移，不能加上 if
if (s[l] == s[r]) f[l][r] = max(f[l][r], f[l + 1][r - 1] + (f[l + 1][r - 1] == r - l - 1 ? 2 : 0));
}
cout << f[1][n] << endl;
return 0;
}
这种回文类型的题目，一般都是讨论两端字符 \(s_i\) 和 \(s_j\) 是否相等，以及舍掉 \(i\) 或者 \(j\) 来转移。