入门级-区间动态规划

# 区间动态规划

---

## 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

---

|例题与练习|
| ---------------------------------------------------------- |
|     [P272合并石子](http://39.99.183.126:8888/p/272)         |
|     [P273石子合并（环形）](http://39.99.183.126:8888/p/273) |

---

### 三、扩展理解

#### 1、优化

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

#### 2、区间小技巧

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

* R = L + len -1
* len = R - L + 1
* L = R - len + 1
---
### 怎样处理环

题目中石子围成一个环，而不是一条链，怎么办呢？

**方法一**：由于石子围成一个环，我们可以枚举分开的位置，将这个环转化成一个链，由于要枚举 $n$ 次，最终的时间复杂度为 $O(n^4)$。

**方法二**：我们将这条链延长两倍，变成 $2\times n$ 堆，其中第 $i$ 堆与第 $n+i$ 堆相同，用动态规划求解后，取 $f(1,n),f(2,n+1),\dots,f(n-1,2n-2)$ 中的最优值，即为最后的答案。时间复杂度 $O(n^3)$。

```cpp
for (len = 2; len <= n; len++)
for (i = 1; i <= 2 * n - 1 - len; i++) {
    int j = len + i - 1;
    for (k = i; k < j; k++)
        f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
}
```