区间dp通常采用递推方式实现，将区间长度作为阶段，将区间左右端点作为状态，在实现时特别强调“先阶段、后状态、再决策”的循环顺序。
在线性dp的实现过程中，不强调阶段的概念，只要在递推过程中按顺序求解状态，自然就是按照阶段进行递推。区间dp不是线性dp，区间dp的实现中要特别注意在最外层加一个对状态的循环。
区间dp通常在一维线性空间上进行，状态通常是二维的，即区间两个端点的坐标。
A[1] A[2] A[3] ...... A[n]
每次只能合并相邻的两个数，合并的代价为这两个数之和，最终要将所有数合并成一个，合并顺序的不同会导致总的代价不同，求合并的最小代价。
将问题的解用将A[1]到A[n]的数字合并为一个的最小代价这一集合属性来表达。
原子集合属性（将A[i]，1 $\leqslant$ i $\leqslant$ n，与A[i]自己合并的最小代价）可以直接得出为0。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[l][r] = min \left\{ \begin{aligned} &f[l][k]+f[k+1][r]+\sum_{i=l}^{r}A[i],l\leqslant k<r&&\text{(以k和k+1为界将A[l...r]分为两部分)} \end{aligned} \right.\]最优合并问题在实现时需要先计算数组A的前缀和数组S，
用以计算$\sum_{i=l}^{r}A[i]$（= S[r] - S[l-1]）。
// 原子集合初始化：f[i][i] = 0 (1<=i<=n)
for (int len = 2; len <= n; len++) { // 阶段：区间长度
for (int l = 1; l+len-1 <= n; l++) { // 状态：左端点
int r = l+len-1; // 状态：右端点
f[l][r] = f[l][l] + f[l+1][r] + S[r] - S[l-1]; // 决策
for (int k = l+1; k < r; ++k) // 决策
f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + S[r] - S[l-1]); // 决策
}
}
// 最终结果：f[1][n]
A[1] A[2] A[3] ...... A[n]
标记该序列的所有子串（子串需要连续）是否是回文串。
将问题的解用A[1...n]的所有子串全部标记完成，且自身是否是回文串（是回文串标记为1，不是标记为0）这一集合属性来表达。
原子集合属性（长度为1和2的序列的所有子串全部标记完成，且自身是否是回文串）可以直接得出（长度为1的子串一定是回文串标记为1，长度为2的子串如果两元素相同是回文串标记为1、如果不同不是回文串标记为0）。
小一级集合的属性到大一级集合的属性的推导式为：
\[f[l][r] = \left\{ \begin{aligned} &f[l+1][r-1]&&\text{(A[l]==A[r])}\\ &0&&\text{(A[l]!=A[r])} \end{aligned} \right.\]// 原子集合初始化：f[i][i] = 1 (1<=i<=n), f[i][i+1] = 1/0 (A[i]==A[i+1]/A[i]!=A[i+1], 1<=i<=n-1), 其他情况 f[i][j] = 0
for (int len = 3; len <= n; len++) {
for (int l = 1; l+len-1 <= n; l++) {
int r = l+len-1;
if (str[l] == str[r])
f[i][j] = f[l+1][r-1];
}
}
// 最终所有子串的标记存在二维数组f中
注意推导式中有一个定值（本题中的0这个值），我们用这个定值来初始化了所有非原子集合的状态，从而导致状态推导发生了变化。原本推导式是f[l][r] = 0，实际代码中直接省略（因为推导式变为f[l][r] = f[l][r]，相当于没有赋值）。
区间dp实现时，务必分清阶段、状态和决策、三者应该按照从外到内的顺序依次循环。
具体来讲，应该是按照自底向上的顺序遍历所有阶段，每个阶段遍历其中的所有状态，利用过去阶段的状态计算当前阶段的状态（即为决策）。