区间dp概述
【问题引入】
石子合并问题
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，这两堆石子的总和记为本次操作的代价。问：将N堆石子合并成一堆石子的最小代价。
例如1 2 3 4，代价最低的合并方法为：
1 2 3 4 —>3 3 4(3)—>6 4(9)—>10(19)
题解：
首先定义状态表示，dp[i][j]表示第i堆到第j堆的最小合并代价。我们枚举分割点k，将区间[i,j]分成[i,k]和[k+1,j]，合并这两个子区间的最小代价，再加上当前合并的代价。
则i~j堆合并的最小代价=min(原来的值，分割点k左部分的最小代价+分割点k右部分的最小代价+合并两堆总重量）。其中合并两堆的总重量，就是第i堆到第j堆的总重量，我们可以搞一个前缀和数组来存储第i堆到第j堆的总重量和。
状态转移方程为dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i]）。其中sum为前缀和数组。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main()
{int n;cin >> n;vector<int> stones(n + 1, 0); // 石子重量vector<int> sum(n + 1, 0); // 前缀和数组vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));// 输入并计算前缀和for (int i = 1; i <= n; ++i) {cin >> stones[i];sum[i] = sum[i - 1] + stones[i];dp[i][i] = 0;}// 区间DP核心for (int len = 1; len <= n; ++len) { // 枚举区间长度for (int i = 1; i + len - 1 <= n; ++i) { // 枚举起点iint j = i + len - 1; // 终点jfor (int k = i; k < j; ++k) { // 枚举分割点kdp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);}}}//第1堆到第n堆的最小合并代价cout << "最小合并代价: " << dp[1][n] << endl;return 0;
}环形石子合并问题
题目连接：P1880 [NOI1995] 石子合并 - 洛谷
对于环状区间，合并区间时就可以从后往前合并，比如环形石子是1~6堆，可以将环形看成是在线性的基础上复制两份。
1 2 3 4 5 6 1 2 3 4 5 6
最后合并完成可能是1~6，2~1，3~2.......
所以我们可以将数组复制两份，再进行线性区间dp即可。
//区间dp
//区间上的最优解
//合并出全局最优解
//环状dp
#include<iostream>
using namespace std;const int INF = 0x7f7f7f7f;
int stones[205];
//最小代价，最大代价
int dpMin[205][205], dpMax[205][205];
int sum[205];//前缀和数组
int n;int main()
{cin >> n;memset(sum, 0, sizeof(sum));memset(dpMin, INF, sizeof(dpMin));memset(dpMax, -1, sizeof(dpMax));for (int i = 1; i <= n; i++){cin >> stones[i];sum[i] = sum[i - 1] + stones[i];dpMin[i][i] = 0;dpMax[i][i] = 0;}//环成链for (int i = 1; i <= n; i++){sum[i + n] = sum[i + n - 1] + stones[i];dpMin[i + n][i + n] = 0;dpMax[i + n][i + n] = 0;}//枚举区间长度for(int len=1;len<=n;len++)for (int j = 1; j+len<= 2*n; j++)//枚举起点{int ends = j + len - 1;//枚举终点for (int i = j; i < ends; i++) //枚举分割点{dpMin[j][ends] = min(dpMin[j][ends], dpMin[j][i] + dpMin[i + 1][ends] + sum[ends] - sum[j - 1]);dpMax[j][ends] = max(dpMax[j][ends], dpMax[j][i] + dpMax[i + 1][ends] + sum[ends] - sum[j - 1]);}}int ans1 = INF, ans2 = 0;for (int i = 1; i <= n; i++){//枚举1-6,2-1,3-2,...找出最大值和最小值ans1 = min(ans1, dpMin[i][i + n - 1]);ans2 = max(ans2, dpMax[i][i + n - 1]);}cout << ans1 << "\n" << ans2 << endl;return 0;
}这里再贴一个记忆化搜索的解法（在题解中学习dalao的解法）
//环形石子合并
#include <iostream>
using namespace std;
const int INF = 0x7f7f7f7f;int A[205], f1[205][205], f2[205][205];
int n, ans;int dfs1(int l, int r) //求出最小值
{if (f1[l][r]) return f1[l][r]; //已经处理过的不必再搜索if (l == r) return f1[l][r] = 0; //l==r时，返回0int res = INF;for (int k = l; k <r; k++) //枚举k分割{res = min(res, dfs1(l, k) + dfs1(k + 1, r) + A[r] - A[l - 1]);}return f1[l][r] = res;
}
int dfs2(int l, int r)
{if (f2[l][r]) return f2[l][r];if (l == r) return f2[l][r] = 0;int res = 0;for (int k = l; k < r; k++){res = max(res, dfs2(l, k) + dfs2(k + 1, r) + A[r] - A[l - 1]);}return f2[l][r] = res;
}
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++)A[i] += A[i - 1];dfs1(1, 2 * n);//1-2n合并的最小值dfs2(1, 2 * n);//1-2n合并的最大值int ans1 = INF, ans2 = 0;for (int i = 1; i <= n; i++){ans1 = min(ans1, f1[i][n+i-1]);ans2 = max(ans2, f2[i][n + i - 1]);}cout << ans1 << "\n" << ans2 << endl;return 0;
}抽卡片
【题目描述】
区间[1,n]每次从中抽出一张牌，直到只剩下最外面的两张牌（第一张和最后一张），每次抽牌的得分是被抽到的牌的数字，和左右相邻牌的数字的乘积。问得分之和最小是多少？
题解：
这里抽牌动作相当于删除数字操作。
因为最后都要删除所有的数字（除了两端的数字），所以我们可以分割一个个小区间删除数字，然后合并区间求最小。
状态表示：dp[i][j]表示抽出第i张到第j-1张的最小得分。这样定义的好处是，最后的结果可以直接表示为dp[2][n]，抽出第2张到第n-1张的最小得分。所以dp[i][j]里是不包含j的。
状态转移方程：
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+num[i-1]*num[k]*num[j]）
//区间dp
//抽卡片
//子区间合并出全局最优解
#include <iostream>
#include <cstring>
using namespace std;
int dp[105][105];
int num[105];//dp[i][j]表示抽出第i到第j-1张牌的最小得分
int main()
{int n;cin >> n;memset(dp, 0x3f, sizeof(dp));//dp初始化为inf，因为求最小值for (int i = 1; i <= n; i++){cin >> num[i];dp[i][i] = 0;//自己取自己初始化为0}for (int len = 1; len <= n; len++)//枚举区间长度{for (int i = 2; i + len <= n + 1; i++)//枚举起点,从2开始，因为不包含两端点{int j = i + len - 1;//枚举终点for (int k = i; k < j; k++)//枚举分割点dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + num[i - 1] * num[k] * num[j]);}}cout << dp[2][n] << endl;//取出第二个位置到第n-1个位置的数return 0;
}括号匹配
【题目描述】
给出一个只包含'[' ']' '('和')'的四种括号组成的字符串，问最多有多少个括号满足完全匹配？
【题解】
状态转移：dp[i][j]表示第i到第j个字符中的最大匹配数。如果s[i]与s[j]匹配，那么dp[i][j]=dp[i+1][j-1]+2。
然后再枚举分割点k，由此可得状态转移方程如下：
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])。
//括号匹配
//区间最优解合并 全局最优解
#include <iostream>
#include <cstring>
using namespace std;int dp[105][105];
int main()
{char s[105];while (scanf("%s", s + 1) != EOF){//dp[i][i]不用处理，因为自己和自己匹配不成功就是0memset(dp, 0, sizeof(dp));int len = strlen(s + 1);for (int l = 1; l <= len; l++)//枚举区间长度for (int i = 1; i + l <= len + 1; i++)//枚举起点{int j = i + l - 1;if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[i] == ']')){dp[i][j] = dp[i - 1][j + 1] + 2;}else//区间找最优{for (int k = i; k < j; k++)//枚举分割点dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);}}cout << dp[1][len] << endl;}return 0;
}整数划分
【问题描述】
给出两个整数n,m，要求在n中加入m-1个乘号，将 n分成m段，求出这m段的最大乘积。
【题解】
首先乘号个数有限，所以状态表示中需要包含乘号的个数。
状态表示:dp[i][j]表示第1到第i个字符里插入j个乘号的最大值。枚举分割点k，1<=k<i，在分割点k处插入乘号，那么dp[i][j]=分割点k左侧插入j-1个乘号的最大值*分割点k右侧的数.
其中在求分割点右侧的数时，我们可以定义一个二维数组num，num[i][j]表示第i个字符到第j个字符 表示的数，那么分割点右侧的数可以表示为num[k+1][i]。
//整数划分
#include <iostream>
#include <cstring>
using namespace std;
#define ll long longint m;
char s[50];//n的字符串形式
ll dp[50][50];//前i个字符中插入j个乘号的最大值
ll num[50][50];//第i个字符到第j个字符表示的数
int main()
{scanf("%s%d", s + 1, &m);int len = strlen(s + 1);//初始化memset(dp, 0, sizeof(dp));memset(num, 0, sizeof(num));for (int i = 1; i < len; i++){for (int j = i; j < len; j++){for (int k = i; k <= j; k++){num[i][j] *= 10;num[i][j] += (s[k] - '0');}}dp[i][0] = num[1][i];//插入0个乘号时等于 第1个数到第i个数本身}for(int j=1;j<m;j++)//乘号个数for (int i = 1; i < len; i++)//第1个字符到第i个字符for (int k = 1; k < i; k++)//枚举分割点dp[i][j] = max(dp[i][j], dp[k][j - 1] * num[k + 1][i]);cout << dp[len][m - 1] << endl;return 0;
}
