概念
主要思想：先在小区间进行 DP 得到最优解，然后再利用小区间的最优解合并求大区间的最优解
区间 DP，一般需要从小到大枚举所有可能的区间。在解题时，先解决小区间问题，然后合并小区间，得到更大区间，直到解决最后的大区间问题。合并的操作一般是把左、右两个相邻的子区间合并
两个难点：枚举所有可能的区间、状态转移方程
复杂度：一个长度为 n 的区间，它的子区间数量级为 O(n^2)，每个子区间内部处理时间不确定，合起来复杂度会大于 O(n^2)。
在编程时，区间 DP 至少需要两层 for 循环，第 1 层的 i 从区间的首部或尾部开始，第 2 层的 j 从 i 开始到结束，i 和 j 一起枚举出所有的子区间。例如：
1、石子合并
问题描述
解题思路
样例的计算过程是：（1）第一次合并：2+4=6；（2）第二次合并：6+5=11；总花费是：6+11=17
DP 的状态如何设计？设 dp[i][j] 为从第 i 堆石子到第 j 堆石子的最小花费，那么 dp[1][n] 就是答案。另外，设 sum[i][j] 为从第 i 到 j 的区间和
为了计算最后的 dp[1][n]，需要考虑所有的可能的合并。这些合并包括：
- 合并之前，dp[i][i]=0, 1<=i<=n
- 两堆合并，如右图
例如：dp[1][2] = dp[1][1] + dp[2][2] + sum[1][2];
总结：dp[i][i+1] = dp[i][i] + dp[i+1][i+1] + sum[i][i+1];
3. 三堆合并，如右图所示
例如合并第 1 堆到第 3 堆，有两种情况，如右图所示
dp[1][3] = min( dp[1][1]+dp[2][3], dp[1][2]+dp[3][3] )+ sum[1][3];
总结：dp[i][i+2] = min( dp[i][i]+dp[i+1][i+2], dp[i][i+1]+dp[i+2][i+2] )+ sum[i][i+2];
4. 推广：第 i 堆到第 j 堆的合并，如右图所示
dp[i][j] = min( dp[i][k] + dp[k+1][j] ) + sum[i][j-i+1], i<=k<=j。这就是状态转移方程
下面代码中方法 Minval() 实现了上述计算过程，其中有 3 层循环：
- 最外面一层循环的变量 len 表示区间 [i,j] 的长度，从 2 到 n；
- 第二层枚举的起点位置 i 从 1 到 n-len，终点通过计算得到，j = i+len;
- 在区间 [i,j] 里枚举每个分割的位置 k
代码（Java）
public class Main
{
final int INF = 1 << 30;
final int N = 300;
int n;
int[] sum = new int[N];
private int Minval1(){
int[][] dp = new int[N][N];
for(int len=1; len<n; len++) //len 是 i 和 j 之间的距离
for(int i=1; i<=n-len; i++){ //从第 i 堆开始
int j = i + len; //到第 j 堆结束
dp[i][j] = INF;
for(int k=i; k<j; k++) //i 和 j 之间用 k 进行分割
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
return dp[1][n];
}
private int Minval2(){
int[][] dp = new int[N][N], s = new int[N][N];
for(int i=1; i<=n; i++){
dp[i][i] = 0;
s[i][i] = i; //初始值
}
for(int len=1; len<n; len++)
for(int i=1; i<=n-len; i++){
int j = i + len;
dp[i][j] = INF;
for(int k=s[i][j-1]; k<=s[i+1][j]; k++) //缩小范围
if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1] < dp[i][j]){
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
s[i][j] = k; //记录 [i,j] 的最优分割点
}
}
return dp[1][n];
}
public static void main(String args[]){
Main m = new Main();
Scanner sc = new Scanner(System.in);
while(!sc.hasNext("#")){ //输入以“#”字符串结束
m.n = sc.nextInt();
m.sum[0] = 0;
for(int i=1; i<=m.n; i++){
int x = sc.nextInt();
m.sum[i] = m.sum[i-1] + x; //从 i 到 j 之间的 sum 值等于 sum[j]-sum[i-1]
}
System.out.println(m.Minval1());
System.out.println(m.Minval2());
}
sc.close();
}
}
理解：区间 [0,n]，对于 len=1 时，从 [i,i+1] 、[i+1,i+2]、……、[n-1,n]子区间找出最小花费，接下来对 len=2，从 [i,i+2]、[i+2,i+4]、……[n-2,n]子区间找出最小花费，接下来对于 len=3……，直到 len=n-1，就可找出 [0,n] 区间的最小花费，即为所求。
对于方法 Minval1() （复杂度为 O(n^3)）是可以优化的，在它的三层循环中，最后一层循环枚举分割点 k 是可以优化的：因为每次运行最后一层循环时都在某个子区间内部寻找最优分割点，该操作在多个子区间里是重复的。如果找到这个最优点后保存下来，用于下一次循环，就能避免重复计算，从而降低复杂度
用 s[i][j] 表示区间 [i,j] 中的最优分割点，第三重循环可以从区间 [i,j-1] 的枚举优化到区间 [ s[i][j-1], s[i+1][j] ] 的枚举。其中 s[][] 值是在前面的第三重循环中已经找到并记录下来的。这样算法复杂度接近 O(n^2)，可解决 n<3000 的问题
理解：[i,j] 的最优分割点 是介于 [i,j-1] 的最优分割点 与 [i+1,j] 的最优分割点 之间的
2、回文串
概念
回文串是正读和反读都一样的字符串
问题描述
解题思路
该题有多种解法，其中一种是把 s 反转得到 s'，求得两者最长公共子序列的长度 l，用 s 的长度减去 l 就是答案。下面用区间 DP 方法求解：
定义状态 dp[i][j] 表示字符串 s 的子区间 s[i,j] 变成回文串的最小花费
另外，在考虑删除和插入的花费时，由于这两种操作是等价的（这头加和那头减一样，即都使之成为回文串），所以只要取这两种操作的最小值就可。用数组 w[] 定义字符的花费。
有以下 3 种情况：
- 如果 s[i] == s[j]，那么 dp[i][j] = dp[i+1][j-1]，如右图：
- 如果 dp[i+1][j] 是回文串，那么 dp[i][j] = dp[i+1][j] + w[i]，如右图：
- 如果 dp[i][j-1] 是回文串，那么 dp[i][j] = dp[i][j-1] + w[j].
总结情况2、3，状态转移方程是：dp[i][j] = min( dp[i+1][j]+w[i], dp[i][j-1]+w[j] ) （理解：增或减去 s[i] 或 s[j]，使原 [i,j] 区间成为回文串）
该程序包含两层循环，外层 i 枚举子区间起点，内层 j 枚举终点。因为需要从小区间扩展到大区间，所以 i 从 s 的尾端开始，逐步回退扩大区间，直到首端
代码（Java）
public class Main {
int n,m;
int[] w = new int[30];
int[][] dp = new int[2005][2005];
char ch;
char[] s = new char[2005]; //给定的字符串
public static void main(String[] args) {
int x,y;
Scanner sc = new Scanner(System.in);
while (!sc.hasNext("#")){ //以 # 字符串结束输入
Main m = new Main();
m.n = sc.nextInt(); //n 是用到的字符个数
m.m = sc.nextInt(); //m 是 s 的长度
sc.skip("\n"); //按照输入样例，需要过滤掉一个换行符
m.s = sc.nextLine().toCharArray();
for(int i=0; i<m.n; i++){
String str = sc.next(); //接受一个字符串
m.ch = str.charAt(0); //读取每个字符的插入和删除的花费
x = sc.nextInt();
y = sc.nextInt();
m.w[m.ch-'a'] = Math.min(x,y); //取其中的最小值
}
for(int i=m.m-1; i>=0; i--) //i 是子区间的起点
for(int j=i+1; j<m.m; j++){ //j 是子区间的终点
if(m.s[i] == m.s[j])
m.dp[i][j] = m.dp[i+1][j-1];
else
m.dp[i][j] = Math.min(m.dp[i+1][j]+m.w[m.s[i]-'a'], m.dp[i][j-1]+m.w[m.s[j]-'a']); //增或减去 s[i] 或 s[j]，使原 [i,j] 区间成为回文串
}
System.out.println(m.dp[0][m.m-1]);
}
sc.close();
}
}
