区间dp：顾名思义就是在区间上进行动态规划，通过合并小区间求解一段区间上的最优解。
常见模板：
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=be;j<en;j++){//割点
dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+割点代价);（max也可以）
}
}
}
http://www.51nod.com/Challenge/Problem.html#!#problemId=1021
1021 石子归并
- 1 秒
- 131,072 KB
- 20 分
- 3 级题
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。
收起
输入
第1行：N（2 <= N <= 100)
第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000)
输出
输出最小合并代价
输入样例
4
1
2
3
4
输出样例
19
解题思路：很明显割点代价为前缀和：sum【en】-sum【be-1】//en为该区间的终点，be为起点
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ri register int
typedef long long ll; inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
inline void output(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch=='-'){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
x=x*f;
}
const int maxn=105;
ll dp[maxn][maxn];
ll sum[maxn];
ll a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[i+1]=sum[i]+a[i];
}
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
dp[i][j]=1e18;
}
}
for(int i=0;i<maxn;i++){
dp[i][i]=0;
}
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=be;j<en;j++){//割点
dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1]);
}
}
}
cout<<dp[1][n];
return 0;
}
四边形不等式优化：
我们可以知道，没有优化的区间dp时间复杂度为O（n^3）,我们可以使用四边形不等式优化时间复杂度为O（n^2）。
这里直接给出四边形不等式的定理：
区间包含性：如果i<=j<m<=n,则满足w【j】【m】<=w【i】【n】
四边形不等式：如果i<=j<m<=n，满足w【i】【m】+w【j】【n】<=w【i】【n】+w【j】【m】（交叉小于包含）
我们假设w函数为割点代价同时满足区间包含性和四边形不等式，那么dp函数也满足四边形不等式。
我们定义m【i】【j】为dp【i】【j】取得最优解时候的割点的坐标
此时有：如果dp满足四边形不等式，有m【i】【j】<=m【i】【j+1】<=m【i+1】【j+1】
关于该定理的证明，有兴趣的可以看这篇博客：点击
接下来用四边形不等式来优化上一道题。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ri register int
typedef long long ll; inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
inline void output(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch=='-'){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
x=x*f;
}
const int maxn=105;
ll dp[maxn][maxn];
ll sum[maxn];
ll a[maxn];
ll m[maxn][maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[i+1]=sum[i]+a[i];
}
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
dp[i][j]=1e18;
}
}
for(int i=0;i<maxn;i++){
dp[i][i]=0;
m[i][i]=i;
}
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=m[be][en-1];j<=m[be+1][en];j++){//割点 割点区间长度为en-be-1，dp区间为en-be，所以直接调用即可
// dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1]);
if(dp[be][en]>=(dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1])){
dp[be][en]=dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1];
m[be][en]=j;
}
}
}
}
cout<<dp[1][n];
return 0;
}
String painter
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7155 Accepted Submission(s): 3464
Problem Description
There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?
Input
Input contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.
Output
A single line contains one integer representing the answer.
Sample Input
zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd
Sample Output
6
7
7
题目大意：
给出两个长度相同的字符串st1，st2，每次可以操作字符串st1内的一段区间，使其变成相同的字符，问，最少可以操作多少次，使得字符串st1与st2相等。
因为字符串st1中某个位置的字符与st2相同，所以直接dp可能很复杂。所以我们可以先假设st1每个位置的字符都与st2不同，此时我们可以定义某个状态dp【i】【j】为区间【i，j】所需的最少操作次数，
我们可以先：dp【i】【j】=dp【i+1】【j】+1，然后该区间的割点为k=【i+1，j】，if（st2【i】==st2【k】）dp【i】【j】=min（dp【i】【j】，dp【i+1】【k】+dp【k+1】【j】），因为st1此区间的字符st2不同，所以我们可以把第i号和第k同时操作。
之后，我们就可以开始考虑st1，st2某些位置可能相同的情况了。首先定义ans【i】，意为前k和字符所需要的最少操作数。
if（st1【i】==st2【i】）ans【i】=ans【i-1】；否则枚举此区间的割点，k，ans【i】=min（ans【k】+dp【k+1】【j】，dp【i】【j】），最后答案即为ans【n】。
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int dp[maxn][maxn];
char ch[maxn],ch1[maxn];
int ss[maxn];
int main(){
while(~scanf("%s%s",ch+,ch1+)){
int len=strlen(ch+);
// printf("%s %s",ch+1,ch1+1);
memset(dp,,sizeof(dp));
for(int i=;i<=len;i++){
dp[i][i]=;
}
for(int l=;l<=len;l++){
for(int be=;be+l<=len;be++){
int en=be+l;
dp[be][en]=dp[be+][en]+;
for(int k=be+;k<=en;k++){
if(ch1[be]==ch1[k])dp[be][en]=min(dp[be+][k]+dp[k+][en],dp[be][en]);
}
}
}
for(int i=;i<=len;i++){
if(ch[i]==ch1[i])
ss[i]=ss[i-];
else{
ss[i]=dp[][i];
for(int k=;k<i;k++){
ss[i]=min(ss[i],ss[k]+dp[k+][i]);
}
}
}
// for(int i=1;i<=len;i++)
printf("%d\n",ss[len]);
}
return ;
}