例题与练习
P272合并石子
P273石子合并（环形）

1、区间合并问题

指在区间上进行递推的场景，求一段区间上的最优解，主要通过合并小区间的最优解进而求得大区间最优解的一种dp算法。

例如－石子合并：

N堆石子排成一列，现要将石子有次序的合并成一堆，规定每次只能选相邻的两堆合并成一堆，代价为合并后的一堆的石子数。
请计算将N堆石头合并成一堆需要的最大代价。

2、递归和记忆搜索

区间合并问题用递归思路是非常好理解的。

[L, R]的区间最优解，必然由两个子区间[L, k]和[k+1, R]合并而来，因此可枚举k的位置求最大值。

定义f(L, R)为[L, R]的最优解，则有：

int f(int L, int R) {
  if(L==R) return 0;
  int ans = 0, d=a[R]-a[L-1];
  for(int k=L; k<R; k++)
    ans = max(ans, f(L,k)+f(k+1, R)+d);
  return ans;
}

递归运算存在大量的重复子区间运算，可用一个数组存储起来。

int _f[N][N];

int f(int L, int R) {
  if(_f[L][R]) return _f[L][R];
  if(L==R) return 0;
  int ans = 0, d=a[R]-a[L-1];
  for(int k=L; k<R; k++)
    ans = max(ans, f(L,k)+f(k+1, R)+d);
  return _f[L][R] = ans;
}

3、dp思路

如果不想用递归，也可以用区间DP的思路，从小区间往大区间的方向进行递推。

for(int len=2; len<=n; len++)
    for(int L=1; L<=n-len+1; L++) {
      int R = L+len-1;
      f[L][R] = 0;
      for(int k=L; k<=R-1; k++)
        f[L][R] = max(f[L][R], f[L][k]+f[k+1][R]+a[R]-a[L-1]);
    }

说明：

• 最外层循环必须是区间长度，从小到大
• 内两层循环固定L，求得R，然后枚举[L, R]里面的每个k

三、扩展理解

1、优化

区间dp的复杂度为O(n^3)，可以利用四边形不等式的原理进行优化。

2、区间小技巧

区间有三个要素，L、R、len，通过其中两个可以求得第三个，要理解和熟练掌握计算技巧：

• R = L + len -1
• len = R - L + 1
• L = R - len + 1