概念：
区间DP就是区间上的DP，先算出小区间的最优解，再由小区间合并推出大区间的最优解。
典例：
一、石子合并。
1.51Nod 1021 石子归并（直线版）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1010;
int n;
int a[maxn],sum[maxn];
int s[maxn][maxn],dp[maxn][maxn];int main()
{scanf("%d",&n);sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];s[i][i]=i; //初始化区间的最优分割点 }// 从小区间向大区间进行递推 for(int d=1;d<n;d++){ //枚举区间长度for(int i=1,j;(j=i+d)<=n;i++){ //枚举区间起点dp[i][j]=INF;for(int k=s[i][j-1];k<=s[i+1][j];k++){ //枚举切割点，构造状态转移方程 //printf("k=%d\n",k);if(dp[i][k]+dp[k+1][j]<dp[i][j]){dp[i][j]=dp[i][k]+dp[k+1][j];s[i][j]=k;}} //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);dp[i][j]+=sum[j]-sum[i-1]; //printf("**dp[%d][%d]=%d,s[%d][%d]=%d\n",i,j,dp[i][j],i,j,s[i][j]);}}printf("%d\n",dp[1][n]);return 0;
}
2. 51Nod 1022 石子归并 V2 (环形)
和直线形差不多，我们需要处理出来间隔为n-1的所有可能，所以区间扩大为2*n-1进行处理，然后取dp[i][i+n-1]的最小值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1010;
int n;
int a[maxn],sum[2*maxn];
int s[2*maxn][2*maxn],dp[2*maxn][2*maxn];int main()
{scanf("%d",&n);sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];s[i][i]=i; //初始化区间的最优分割点 }for(int i=n+1;i<2*n;i++){sum[i]=sum[i-1]+a[i-n];s[i][i]=i;}// 从小区间向大区间进行递推 for(int d=1;d<n;d++){ //枚举区间长度for(int i=1,j;i<=2*n-d;i++){ //枚举区间起点j=i+d;dp[i][j]=INF;for(int k=s[i][j-1];k<=s[i+1][j];k++){ //枚举切割点，构造状态转移方程 //printf("k=%d\n",k);if(dp[i][k]+dp[k+1][j]<dp[i][j]){dp[i][j]=dp[i][k]+dp[k+1][j];s[i][j]=k;}} //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);dp[i][j]+=sum[j]-sum[i-1]; //printf("**dp[%d][%d]=%d,s[%d][%d]=%d\n",i,j,dp[i][j],i,j,s[i][j]);}}int mn=INF;for(int i=1;i<=n;i++){mn=min(mn,dp[i][i+n-1]);}printf("%d\n",mn);return 0;
}
二、括号匹配问题。
三、整数划分问题。