区间DP是线性DP的拓展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的那些元素合并而来有很大的关系。令状态f(l, r)表示将下标位置l到r的所有元素合并能获得的价值的最大值，那么f(l, r)=max{f(l, k)+f(k+1, r)+cost}，cost为将这两组元素合并起来的代价。

区间DP的特点：

合并：即将两个或多个部分进行整合，当然也可以反过来。

特征：能将问题分解为能两两合并的形式。

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优解得到原问题的最优解。

通常区间DP问题常见的基本流程为：

1. 从小到大枚举区间大小len
2. 枚举区间左端点l，同时根据区间大小len和左端点计算出区间右端点r=l+len-1
3. 通过状态转移方程求f[l][r]的值

题目：

516. 最长回文子序列

参考：

[1] https://oi-wiki.org/dp/interval/