区间DP
到目前为止，我们介绍的线性 DP 一般从初态开始，沿着阶段的扩张向某个方问递推，直至计算出目标状态，区间 DP 也属于线性 DP 中的一种，它以“区间长度”作为 DP 的“阶段”，使用两个坐标（区间的左、右端点），描述每个维度。在区间 DP 中，一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来，因此，区间 DP 的决策往往就是划分区间的方法。区间 DP 的初态一般就由长度为 1 的“元区间”构成。这种向下划分、再向上递推的模式与某些树形结构，例如线段树，有很大的相似之处。我们把区间 DP 作为线性 DP 中一类重要的分支单独进行讲解，将使读者更容易理解下一节树形 DP 的内容。同时，借助区间 DP 这种与树形相关的结构，我们也将提及记忆化搜索——其本质是动态规划的递归实现方法。
石子合并
题目描述
设有 \(N\) 堆石子排成一排，其编号为 \(1，2，3，\dots，N\)。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 \(N\)
堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 \(N\) 表示石子的堆数 \(N\)。
第二行 \(N\) 个数，表示每堆石子的质量(均不超过 \(1000\))。
输出格式
输出一个整数，表示最小代价。
数据范围
\(1 \le N \le 300\)
输入样例：
4
1 3 5 2
输出样例：
22
若最初的第 \(l\) 堆石子和第 \(r\) 堆石子被合并成一堆，则说明 \(l \sim r\) 之间的每堆石子也己经被合并，这样 \(l\) 和 \(r\) 才有可能相邻。因此，在任意时刻，任意一堆石子均可以用一个闭区间 \([l,r]\) 来描述，表示这堆石子是由最初的第 \(l \sim r\) 堆石子合并而成的，其重量为 \(\sum_{i=1}^{r}A[i]\)。另外，一定存在一个整数 \(k(l \le k <r)\) ，在这堆石子形成之前，先有第 \(l \sim k\) 堆石子（闭区间 \([l,k]\)）被合并成一堆，第 \(k+1 \sim r\) 堆石子（闭区间 \([k+1,r]\)）被合并成一堆，然后这两堆石子才合并成 \([l,r]\)。
对应到动态规划中，就意味省两个长度较小的区间上的信息向一个更长的区间发生了转移，划分点 \(k\) 就是转移的决策。自然地，应该把区间长度 \(len\) 作为 DP 的阶段。不过，区间长度可以由左端点和右端点表示出，即 \(len = r-l+1\)。 本着动态规判“选择最小的能覆盖状态空间的维度集合”的思想，可以只用左、右端点表示 DP 的状态。
设 \(F[l,r]\) 表示把最初的第 \(l\) 堆到第 \(r\) 堆石子合并成一堆，需要消耗的最少体力。则容易写出状态转移方程：
\[F[l,r]=\min_{l \le < r} \lbrace F[l,k]+F[k+1,r] \rbrace + \sum\limits_{i=l}^{r}A_i \]初值：\(\forall l \in [1,N],F[l,l]=0, \text{其余为正无穷}\)
目标：\(F[1,N]\)
最后强调，编程实现动态规划的状态转移方程时，务必分清阶段、状态与决策，三者应该按照从外到内的顺序依次循环。而 \(\sum_{i=l}^{r}A_i\) 可以使用前缀和计算。
状态数量是 \(N^2\) 个，状态计算 \(N\) 次，所以总的时间复杂度是 \(O(N^3)\)。
#include <iostream>
using namespace std;
const int N = 310, INF = 0x3f3f3f3f;
int n; // n堆石子
int s[N]; // 前缀和数组，表示前i堆石子的质量和
int f[N][N]; // f[l][r]表示合并[l,r]区间内的石子的最小代价
int main()
{
cin >> n;
// 预处理前缀和
for (int i = 1; i <= n; i ++ ) cin >> s[i], s[i] += s[i - 1];
// 枚举每个阶段（区间长度），len等于1时只有一堆，代价为0，而堆中变量自动初始化为0，不需要操作，所以从2开始循环
for (int len = 2; len <= n; len ++ )
// 枚举状态表示的区间左端点
for (int l = 1; l <= n - len + 1; l ++ ) {
// 通过区间长度与左端点计算出右端点
int r = l + len - 1;
// 每次处理前将该状态初始化为正无穷
f[l][r] = INF;
// 循环处理每一个决策
for (int k = l; k < r; k ++ )
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
cout << f[1][n] << endl;
return 0;
}