两个难点：
1、枚举所有可能的区间
2、状态转移方程
1274：【例9.18】合并石子 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5121 通过数: 3243 【题目描述】 在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 计算出将Ｎ堆石子合并成一堆的最小得分。 【输入】 第一行为一个正整数N (2≤Ｎ≤100)； 以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。 【输出】 一个正整数，即最小得分。 【输入样例】 7 13 7 8 16 21 4 18 【输出样例】 239
状态：f[i][j]表示区间i到j之间的最小花费，那么f[1][n]就是最后的答案
状态转移方程：f[i][j]=f[i][k]+f[k][j]+sum[i][j-i+1]；
所以在这里需要求一个前缀和sum[i][j-i+1] 就相当于sum[j]-sum[i-1]
#include <bits/stdc++.h> using namespace std; const int N=130,inf=0x3f3f3f;; int sum[N],c[N]; int f[N][N],n,x,t; inline int read() { int x=0;char y=‘*‘,z=getchar(); while(z<‘0‘||z>‘9‘) y=z,z=getchar(); while(z>=‘0‘&&z<=‘9‘) x=(x<<3)+(x<<1)+(z-‘0‘),z=getchar(); return y==‘-‘?-x:x; } int main() { n=read(); for(int i=1;i<=n;i++){ x=read(); sum[i]=sum[i-1]+x;//前缀和 } memset(f,127/3,sizeof(f)); for(int i=1;i<=n;i++) f[i][i]=0; for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) for(int k=i;k<=j-1;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]); cout<<f[1][n]<<endl; return 0; }
上述代码有三重循环，所以复杂度为O(n3)，所以这种问题只能处理n<250的问题；
该问题在动态规划中也有写过，咳咳还有一个环形的情况
优化：
平行四边形优化原理：是区间DP常用的优化方法；主要思想就是用s[i][j]来存储最优分割点
只需要更改几个地方:(红色)！！
#include <bits/stdc++.h> using namespace std; const int N=130,inf=0x3f3f3f;; int sum[N],c[N],s[N][N]; int f[N][N],n,x,t; inline int read() { int x=0;char y=‘*‘,z=getchar(); while(z<‘0‘||z>‘9‘) y=z,z=getchar(); while(z>=‘0‘&&z<=‘9‘) x=(x<<3)+(x<<1)+(z-‘0‘),z=getchar(); return y==‘-‘?-x:x; } int main() { n=read(); for(int i=1;i<=n;i++){ x=read(); sum[i]=sum[i-1]+x;//前缀和 } memset(f,127/3,sizeof(f)); for(int i=1;i<=n;i++) { f[i][i]=0;s[i][i]=i; } for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) for(int k=s[i][j-1];k<=s[i+1][j];k++) if(f[i][j]>f[i][k]+f[k+1][j]+sum[j]-sum[i-1]) { f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]); s[i][j]=k; } cout<<f[1][n]<<endl; return 0; }
这样优化以后，复杂度更加接近于O(n2)，科技解决接近n<3000的问题了~
回文串是正读反读都是一样的字符串，最经典的问题就是：给定一个字符串，通过增加或者删除得到一个回文串。
poj 3280 给出一个由m中字母组成的长度为n的串，给出m种字母添加和删除花费的代价，求让给出的串变成回文串的代价。
我们定义dp [ i ] [ j ] 为区间 i 到 j 变成回文的最小代价。
那么有三种情况：
首先：对于一个串如果s【i】==s【j】，那么dp【i】【j】=dp【i+1】【j-1】
其次：如果dp【i+1】【j】是回文串，那么dp【i】【j】=dp【i+1】【j】+min（add【i】，del【i】）；
最后，如果dp【i】【j-1】是回文串，那么dp【i】【j】=dp【i】【j-1】 + min（add【j】，del【j】）；
参考代码：
int main() { int n,m,t,i,j; while(~scanf("%d%d",&n,&m)) { scanf("%s",s); for(i=0; i<n; i++) { scanf("%s",c); scanf("%d%d",&cost[c[0]-‘a‘],&t); if(t<cost[c[0]-‘a‘]) cost[c[0]-‘a‘]=t; } memset(dp,0,sizeof(dp)); for(i=m-1; i>=0; i--) { for(j=i+1; j<m; j++) { dp[i][j]=min(dp[i+1][j]+cost[s[i]-‘a‘],dp[i][j-1]+cost[s[j]-‘a‘]); if(s[i]==s[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); } } printf("%d\n",dp[0][m-1]); } return 0; }
例题：回文词
Description 回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。 Input 第一行包含一个整数N，表示给定字符串的长度（3≤N≤50 00）。 第二行是一个长度为N的字符串。字符串仅由大写字母“A”到“Z”，小写字母“a”到“z”和数字“0”到“9”构成。大写字母和小写字母将被认为是不同的。 Output 只有一行，包含一个整数，表示需要插入的最少字符数。 Sample Input 5 Ab3bd Sample Output 2
用字符串长度来减去（原字符串与反串）的最长公共子序列长度只能得到70分
还是得用这种记忆化的dp才能AC:
#include <bits/stdc++.h> using namespace std; const int N=5005,inf=0x3f3f3f;; int f[N][N],n,x; char s[N],rs[N]; int dfs(int i,int j) { if (f[i][j]!=0xfffffff) return f[i][j]; if (s[i-1]==s[j-1]) return f[i][j]=dfs(i+1,j-1); else { f[i][j]=min(dfs(i+1,j),dfs(i,j-1))+1; } return f[i][j]; } int main() { scanf("%d",&n); cin>>s; for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) { f[i][j]=0xfffffff;f[i][i]=0; } f[1][n]=dfs(1,n); printf("%d",f[1][n]); return 0; }
区间动态规划例题：（做到就来补一补）
原文：https://www.cnblogs.com/sunny99/p/12644022.html
