更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19526744

大意

$n = 2000$ 的石子合并。

思路

首先，区间 DP 是 $\mathcal{O}(n ^ 3)$ 的，对于这个题显然是不合适的。

我们考虑优化。

令 $G(k) = f(i, k) + f(k + 1, j)$。

我们接下来证明这个 $G(k)$ 为凸函数，则 $G(k) \le \displaystyle\frac{G(k - 1) + G(k + 1)}{2}$

令 $\Delta G(k) = G(k + 1) - G(k)$

$\Delta G(k) = [f(i, k + 1) - f(i, k)] - [f(k + 1, j) - f(k + 2, j)]$

左边的 $f(i, k + 1) - f(i, k)$ 随着 $k$ 的增大递增。

右边的 $f(k + 1, k) - f(k + 2, j)$ 随着 $k$ 的增大递减。

递增 - 递减 = 递增。

故 $G(k)$ 单调递增，则 $G(k)$ 为凸函数，最大值在端点处取得。

所以最终的转移式为：

$$f(i, j) = \max(f(i+1, j), f(i, j-1)) + w(i, j)$$