区间dp（竞赛）

一、介绍

区间 dp 其实就是左右端点固定之后，用已经得出的小区间来更新大区间答案的 dp 方式。

非常重要的要素：小区间得到大区间，衍生出来的问题就是对于大区间如何划分成若干小区间，这直接决定了方程的书写。之后的例题中慢慢体会。

一般步骤：先固定长度 len，再固定左端点 i，右端点 j 自然固定。

边界条件是当 i == j 时，dp[i][j] = ...

二、例题

1、回文字串

P1435 [IOI 2000] 回文字串 - 洛谷

#include <bits/stdc++.h>
using namespace std;// dp[i][j]表示字符串在[i, j]中变成回文串最小插入数量
// s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1];
// s[i] != s[j]: j == i + 1: dp[i][j] = 1;
//                     else: dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
// i依赖i+1，j依赖j-1，所以顺序：i从大到小，j从小到大，且i <= j
// dp[n][n] = 0;
int dp[1010][1010];
int main()
{string s;cin >> s;int n = s.size();for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(i == j)dp[i][j] = 0;else if(i == j - 1){if(s[i] == s[j])dp[i][j] = 0;else dp[i][j] = 1;}else {if(s[i] == s[j])dp[i][j] = dp[i + 1][j - 1];else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;}}}cout << dp[0][n - 1];return 0;
}

这道题由于 dp 表的含义，可以把 [i, j] 区域内的字符串看作已经是回文的，所以对于区间的划分只会在端点处，即 dp[i + 1][j] 和 dp[i][j - 1]

2、Treats for the Cows G/S

P2858 [USACO06FEB] Treats for the Cows G/S - 洛谷

#include <bits/stdc++.h>
using namespace std;const int N = 2010;
int a[N];
int dp[N][N];
// dp[i][j]表示在区间[i, j]中选出的最大价值
// 一定是小区间到大区间更新
// dp[i][j] = max(dp[i + 1][j] + x * a[i], dp[i][j - 1], x * a[j]);
// 区间dp顺序可以枚举长度加左端点，这样就能实现小区间到大区间
// 初始化：没有就全是0int main() 
{int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for(int len = 1; len <= n; len++){for(int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;int x = n - len + 1;dp[i][j] = max(dp[i + 1][j] + x * a[i], dp[i][j - 1] + x * a[j]);}}cout << dp[1][n];return 0;
}

这道题也是明确规定，你只能从两端取食物，所以分组还是端点处。

3、石子合并（弱化版）

P1775 石子合并（弱化版） - 洛谷

#include <bits/stdc++.h>
using namespace std;
int a[1010];
int n;
const int INF = 0x3f3f3f3f;
int dp[1010][1010];// dp[i][j]表示合并[i, j]区域的最小代价，所以是任意分成[i, k], [k + 1, j]的两组
// dp[i][j] = dp[i][k] + dp[k + 1][j];
// 初始化条件：i == j时，dp[i][j] = 0;
// 前缀和优化
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];a[i] += a[i - 1];}for(int len = 2; len <= n; len++){for(int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;dp[i][j] = INF;for(int k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[j] - a[i - 1]);}}cout << dp[1][n];return 0;
}

这道题说的是你可以任意选择相邻的两个数进行合并，所以 dp[i][j] 的划分一定不能是只在端点处，而是要分成 dp[i][k], dp[k + 1][j] 两个区间。

4、石子合并

P1880 [NOI1995] 石子合并 - 洛谷

// 遇到环形问题可以数组复制，此时要明确起点和遍历长度
#include <bits/stdc++.h>
using namespace std;
int n;
int a[210];
int s[210];
int dp1[210][210];
int dp2[210][210];
const int INF = 0x3f3f3f3f;int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];a[i + n] = a[i];}for(int i = 1; i <= 2 * n; i++)s[i] = a[i] + s[i - 1];int ans1 = INF;int ans2 = -INF;for(int len = 2; len <= n; len++){for(int i = 1; len + i - 1 <= 2 * n; i++){int j = i + len - 1;dp1[i][j] = INF;for(int k = i; k < j; k++){dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + s[j] - s[i - 1]);dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + s[j] - s[i - 1]); if(len == n){ans1 = min(ans1, dp1[i][j]);ans2 = max(ans2, dp2[i][j]);}}}}cout << ans1 << endl;cout << ans2 << endl;return 0;
}

这道题思考方式和上一题一样，只不过是环形数组，对于环形数组，只要开两倍空间模拟线性，然后固定好长度 1 ~ n，固定好左端点 1 ~ 2 * n - len，遍历就没有任何问题。

5、248 G

P3146 [USACO16OPEN] 248 G - 洛谷

#include <bits/stdc++.h>
using namespace std;
int n;
int a[300];
int dp[300][300];// dp[i][j]表示[i, j]区域尝试合并之后的最大值，dp[i][j] == 0就代表区间不能合并
// 区域[i, j]被分成[i, k], [k + 1, j]，如果二者相等且不是0，那就可以合并，不然dp[i][j]还是0，即不能合并
// 边界问题：i == j时区间可以合并，大小是a[i]
int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];int ans = 0;for(int len = 1; len <= n; len++){for(int i = 1; i + len - 1 <= n; i++){if(len == 1){dp[i][i] = a[i];ans = max(ans, dp[i][i]);}else {int j = i + len - 1;for(int k = i; k < j; k++){if(dp[i][k] == dp[k + 1][j] && dp[i][k] != 0){dp[i][j] = max(dp[i][j], dp[i][k] + 1);ans = max(ans, dp[i][j]);}}}}}cout << ans;return 0;
}

也是在区间里面任意找相邻且相等的数，所以分成 dp[i][k], dp[k + 1][j] 两个区间。

三、总结

所以理解用小区间更新大区间，自然而然就要想到如何正确的划分小区间也是非常重要的。