一、区间动态规划
区间动态规划是动态规划中的一类题，下面先引入几个题目，最后总结一下此类问题的相关解题思路
二、例题
1.[Daimayuan Online Judge.石子合并]
题目描述
有 \(n\) 堆石子排成一排，第 \(i\) 堆石子有 \(a_i\) 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？
输入格式
第一行一个数字 \(n\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\)。
输出格式
一行一个整数，表示答案。
输入样例
3
1 2 3
输出样例
9
数据范围
对于所有数据，保证 \(1≤n,a_i≤500\)。
解题思路
对于第 \(i\) 和 \(i+1\) 堆石子合并，代价为 \(a_i+a_{i+1}\)，\(1≤i<n\)。因此需要预处理前缀和
- 状态表示：\(f[i][j]\) 表示合并 \(i\) 到 \(j\) 堆石子的代价，需要求解最小值
- 状态计算：合并第 \(i\) 到 \(j\) 堆石子，可分为合并 \(f[i][k]\) 和 \(f[k+1][j]\)，\(k\in[i,j)\)，故 \(f[i][j]=f[i][k]+f[k+1][j]+a_i+a_{i+1}+...+a_{j}\)，枚举分界点 \(k\) 求解最小值
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int a[N], s[N];
int f[N][N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int l = i, r = i + len - 1;
f[l][r] = 0x3f3f3f3f;
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]);
}
}
printf("%d\n", f[1][n]);
return 0;
}
2.[Daimayuan Online Judge.括号序列]
题目描述
给定一个长度为 \(n\) 的字符串 \(s\)，字符串由 \((, ), [, ]\) 组成，问其中最长的合法子序列有多长？也就是说，我们要找到最大的 \(m\)，使得存在 \(i_1,i_2,…,i_m\) 满足 \(1≤i_1<i_2<⋯<i_m≤n\) 并且 \(s_{i_1}s_{i_2}…s_{i_m}\) 是一个合法的括号序列。
合法的括号序列的定义是：
- 空串是一个合法的括号序列。
- 若 \(A\) 是一个合法的括号序列，则 \((A), [A]\) 也是合法的括号序列。
- 若 \(A, B\) 都是合法的括号序列，则 \(AB\) 也是合法的括号序列。
输入格式
第一行一个数字 \(n\)。
接下来一行，一个长度为 \(n\) 的字符串 \(s\)。
输出格式
一行一个整数，表示答案。
输入样例
10
]]][()]])[
输出样例
4
数据范围
对于所有数据，保证 \(1≤n≤500\)。
解题思路
- 状态表示：\(f[i][j]\) 表示 \(i\) 到 \(j\) 的合法括号序列，属性值为长度
- 状态计算：根据合法括号序列的定义，对于 \(f[i][j]\)，如果 \(s_i=s_j\)，则 \(f[i][j]=f[i++1][j-1]+2\)，否则 \(f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j+1]))\)；另外，根据 “若 \(A, B\) 都是合法的括号序列，则 \(AB\) 也是合法的括号序列”，可以枚举分界点，进行括号序列的拼接，即 \(f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]),k\in[i,j)\)，且这种情况可以包含 \(s_i\neq s_j\) 这种情况，减少代码量
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
char s[N];
int f[N][N];
int main() {
scanf("%d%s", &n, s + 1);
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int l = i, r = i + len - 1;
if (s[l] == '[' && s[r] == ']' || s[l] == '(' && s[r] == ')')
f[l][r] = f[l + 1][r - 1] + 2;
for (int k = l; k < r; k++)
f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
}
}
printf("%d\n", f[1][n]);
return 0;
}
3.[Daimayuan Online Judge.石子合并2]
题目描述
有 \(n\) 堆石子围成一个圈，第 \(i\) 堆石子有 \(a_i\) 颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？
输入格式
第一行一个数字 \(n\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\)。
输出格式
一行一个整数，表示答案。
输入样例
3
1 3 2
输出样例
9
数据范围
对于所有数据，保证 \(1≤n≤250,1≤a_i≤500\)。
解题思路
典型的环型区间动态规划问题，此类题目可以将序列重复一遍，也就是令 \(a_i=a_{i+n}\)，这样当作一个链式区间动态规划问题进行求解，这样的话先求解整个的区间结果，最后取其中的一部分即可，结合本题目就是，先求解 \(a_1\) 到 \(a_{2n}\) 的最小代价，然后取其中长度为 \(n\) 的合并代价取最小值
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int a[N], s[N];
int f[N][N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
}
for (int i = 1; i <= 2 * n; i++)
s[i] = s[i - 1] + a[i];
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= 2 * n; i++) {
int l = i, r = i + len - 1;
f[l][r] = 0x3f3f3f3f;
for (int k = i; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
ans = min(ans, f[i][i + n - 1]);
printf("%d\n", ans);
return 0;
}
三、总结
区间动态规划的问题的求解还是比较有套路的，基本状态表示都是二维表示区间的左右端点，当然某些问题可能涉及到最后在哪个端点处，这样就需要额外考虑一维，用 \(0\) 和 \(1\) 两种状态来区分。