所谓区间dp,就是在一个区间上进行的dp， 一般通过将大区间分割成小区间进行dp，常见的经典题型总结如下：
乘积最大
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入 程序的输入共有两行： 第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输出 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 样例输入 4 2 1231 样例输出 62 提示 由于数据比较弱，可以用long long通过 #include<iostream> #include<cstdlib> #include<cstdio> using namespace std; long long a[50][50]; long long f[50][50]; long long t[50]; int main() { long long n,k; long long s; cin>>n>>k; cin>>s; for (int i=n;i>=1;i--) { t[i]=s; s/=10; } for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) a[i][j]=a[i][j-1]*10+t[j];//a[i][j]存储从i到j的值 for (int i=1;i<=n;i++) f[i][0]=a[1][i];//dp初始化，f[i][j]表示前i个数插入j个乘号,一开始插入0个乘号，f[i][0]等于从1到i的值 for (int i=1;i<=n;i++)//从第1个数开始 for (int j=1;j<=k;j++)//枚举k个乘号 for (int p=0;p<i;p++)//从1到i之间插入乘号 f[i][j]=max(f[i][j],f[p][j-1]*a[p+1][i]);//转移方程 cout<<f[n][k]<<endl; return 0; } 石子合并： 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成 一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 210 int dp[N][N],sum[N]; int main() { int n; while(~scanf("%d",&n)) { int a[N];sum[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; //sum[i]是数组的前缀和 } memset(dp,0,sizeof(dp)); int i,j,l,k; for(l = 2; l <= n; ++l) //从长度为2的区间开始，一直枚举到长度为n的区间，从合并两个，到合并三个，最后合并n个。 { for(i = 1; i <= n - l + 1; ++i) //起始位置为1，n-l+1是最后一个区间的起始位置 { j = i + l - 1;//通过起始位置和区间长度求出区间终止位置 dp[i][j] = 2100000000; for(k = i; k < j; ++k)//这一步在进行区间分割 //dp[i][j]表示合并i到j区间内的最小代价。枚举i到j中的点k，看有没有一种情况是合并i到k,k+1到j（可以保证i到k和k+1到j都是最优值，因 //为i到k和k+1到j的区间长度肯定小于i到j的长度，而我们是从区间最小的开始递推的），再将这两堆合并起来的代价比原来的代价低，如果有 //则更新 { dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1]); } } } printf("%d\n", dp[1][n]); } return 0; } #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define inf 1000000000; using namespace std; int a[205]; int sum[205][205]; int dp1[205][205];//线性合并最大 int dp2[205][205];//线性合并最小 int dp3[205][205];//环状合并最大 int dp4[205][205];//环状合并最小 int main() { int n,i,j,k,length; scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); memset(dp3,0,sizeof(dp3)); memset(dp4,0,sizeof(dp4)); for(i=1;i<=n;i++) { scanf("%d",&a[i]); a[n+i]=a[i]; } for(i=1;i<=2*n;i++) for(j=i;j<=2*n;j++) i==j?sum[i][j]=a[i]:sum[i][j]=sum[i][j-1]+a[j]; for(i=1;i<=2*n;i++) for(j=i;j<=2*n;j++) { if(i==j) { dp1[i][j]=0; dp2[i][j]=0; dp3[i][j]=0; dp4[i][j]=0; } else { dp1[i][j]=0; dp2[i][j]=inf; dp3[i][j]=0; dp4[i][j]=inf; } } for(length=2;length<=n;length++) { for(i=1;i<=n-length+1;i++)//起点 { j=i+length-1;//终点 for(k=i;k<j;k++) { dp1[i][j] = max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[i][j]); dp2[i][j] = min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[i][j]); } } } for(length=2;length<=n;length++) { for(i=1;i<=2*n-length+1;i++) { j=i+length-1; for(k=i;k<j;k++) { dp3[i][j]=max(dp3[i][j],dp3[i][k]+dp3[k+1][j]+sum[i][j]); dp4[i][j]=min(dp4[i][j],dp4[i][k]+dp4[k+1][j]+sum[i][j]); } } } printf("%d %d\n", dp2[1][n],dp1[1][n]); int circle_min=inf; int circle_max=0; for(i=1;i<=n;i++) { circle_min=min(dp4[i][i+n-1],circle_min); circle_max=max(dp3[i][i+n-1],circle_max); } printf("%d %d",circle_min,circle_max); return 0; }
括号匹配：
给出一串的只有()[]四种括号组成的串，求解需要最少添加括号数让串中的所有括号完全匹配。
思路：dp[i][j]表示 i 到 j 最多的匹配个数，dp[i][j] = max（dp[i][j], dp[i][k] + dp[k+1][j]);
#include <iostream> #include <cstring> #include <algorithm> #include <string> using namespace std; const int N = 120; int dp[N][N]; int main() { string s; while(cin>>s) { if(s=="end") break; memset(dp,0,sizeof(dp)); for(int i=1;i<s.size();i++)//枚举区间长度，0到i为一个区间 { for(int j=0,k=i;k<s.size();j++,k++)//k是右边界，不能超出字符串长度 { if(s[j]=='('&&s[k]==')' || s[j]=='['&&s[k]==']') //如果左右边界相等，则更新 dp[j][k]=dp[j+1][k-1]+2; for(int f=j;f<k;f++) // 区间分割，更新i到j最多匹配个数。因为区间从最短往前递推，可以保证j到f，f+1到k都是最优值。 dp[j][k]=max(dp[j][k],dp[j][f]+dp[f+1][k]); } } cout<<dp[0][s.size()-1]<<endl; } return 0; }