区间dp及经典例题
区间dp：
区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
主要思路：既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。
例题1：括号匹配
We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()]
while the following character sequences are not:
(, ], )(, ([)], ([(]
Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.
Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].
Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.
Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
Sample Input
((()))
()()()
([]])
)[)(
([][][)
end
Sample Output
6
6
4
0
6
用二维数组f[i][j]表示从i~j的最大匹配数，还有个比较重要的思想是拆分思想，就是把f[i][j],拆分为f[i][k]+f[k+1][j]两部分的和，在取最大，就是dp的选择过程。
AC代码：
#include<iostream>
#include<cstring>
using namespace std;
int f[110][110];
int main()
{
string a;
while(cin>>a&&a!="end")
{
memset(f,0,sizeof(0));//初始化
int n=a.length();
for(int d=2;d<=n;d++)//间隔长度，括号总是成对出现，所以间隔取2.
{
for(int i=0;i<n;i++)
{
int j=i+d-1;//每一段的右结点
if(j>n) break;
if((a[i]=='('&&a[j]==')')||(a[i]=='['&&a[j]==']'))//匹配
f[i][j]=f[i+1][j-1]+2;//+2是因为括号是一对
else
f[i][j]=f[i+1][j-1];//不匹配则不变
for(int k=i;k<j;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);//核心，拆分过程
}
}
}
cout<<f[0][n-1]<<"\n";
}
}
例题2：（经典）石子合并问题--直线版
一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。
每组第一行为n(n<=100)，表示有n堆石子，。
二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）
Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3
1 2 3
Sample Output
9 11
这个题是区间dp的经典问题，很容易联想到贪心算法里面的合并果子，但那个是任意两堆可以合并，但是这个题中只能是相邻的合并，嗯，That's good~。
和上个题一样，我们需要设置maxx[i][j]和minn[i][j]分别来储存从i~j堆的合并最小消耗值。并用sum[i]记录一下前缀和。
复杂度O(n3)
AC代码：
#include<bits/stdc++.h>
using namespace std;
int maxx[110][110];
int minn[110][110];
int sum[110];
int main()
{
int n;
while(cin>>n)
{
sum[0]=0;
memset(maxx,0,sizeof(maxx));
memset(minn,0,sizeof(minn));
for(int i=1;i<=n;i++)
{
cin>>sum[i];
sum[i]+=sum[i-1];
}
for(int d=1;d<=n;d++)
{
for(int i=1;i+d<=n;i++)
{
int j=i+d;
minn[i][j]=99999999;//除了min[i][i]都赋值最大，因为自己合并自己消耗值是0.
for(int k=i;k<j;k++)
{
maxx[i][j]=max(maxx[i][j],maxx[i][k]+maxx[k+1][j]+sum[j]-sum[i-1]);
minn[i][j]=min(minn[i][j],minn[i][k]+minn[k+1][j]+sum[j]-sum[i-1]);
}
}
}
cout<<minn[1][n]<<' '<<maxx[1][n]<<'\n';
}
}
但是复杂度非常高，如果n<=1000就无法通过了，所以我们需要考虑用四边形不等式优化，接近O(n2).
（暂时还不会，会了再贴上）
例题3：（升级）石子合并问题--圆形版
在圆形操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
Input
输入有多组测试数据。
每组第一行为n(n<=100)，表示有n堆石子，。
二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）
Output
每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。
Sample Input
3
1 2 3
Sample Output
9 11
与上个题大体相同，不同的地方在于这些石子是首位相接的环状，也就是说第一个与最后一个也能够进行合并。
所以就比较好想了，我们可以设置二倍大小的数组，中间的dp过程相同，唯一不同的就是dp结束后，需要寻找开始和结束点，来使消耗值最小。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int maxx[220][220];
int minn[220][220];
int sum[220];
int a[110];
int main()
{
int n;
while(cin>>n)
{
sum[0]=0;
memset(maxx,0,sizeof(maxx));
memset(minn,0,sizeof(minn));
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=n+1;i<=2*n;i++)//2*n!
sum[i]=sum[i-1]+a[i-n];
for(int d=1;d<=n*2;d++)
{
for(int i=1;i+d<=n*2;i++)
{
int j=i+d;
minn[i][j]=99999999;//除了min[i][i]都赋值最大，因为自己合并自己消耗值是0.
for(int k=i;k<j;k++)
{
maxx[i][j]=max(maxx[i][j],maxx[i][k]+maxx[k+1][j]+sum[j]-sum[i-1]);
minn[i][j]=min(minn[i][j],minn[i][k]+minn[k+1][j]+sum[j]-sum[i-1]);
}
}
}
int ansmin=99999999;
int ansmax=0;
for(int i=1;i<=n;i++)
{
ansmin=min(ansmin,minn[i][i+n-1]);
ansmax=max(ansmax,maxx[i][i+n-1]);
}
cout<<ansmin<<' '<<ansmax<<'\n';
}
}