Road Map

区间 DP

区间 DP也属于 线性 DP的一种，以 ”区间长度“ 作为 DP 的 ”阶段“， 使用 两个坐标（区间的左右断点）描述每个维度。

在区间 DP 中，一个状态由若干个比他更小且包含于他的区间所代表的状态转移而来，因此区间 DP 的决策往往就是划分区间的方法。

区间 DP 的初态一般由长度为 1 的”元区间“构成。

这种向下划分，再向上递推的模式与某些树形结构，如线段树，有很大相似之处。

借助区间 DP 这种与树形相关的结构，我们也将提及记忆化搜索 -- 本质是 DP 的递归实现方法。

特点

• 区间 DP 在状态计算的时候一定要 认真 划分好 边界 和 转移; 因为 区间边界 搞错状态 转移方程 是非常常见的错误。

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

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

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

• 一般用二维数组表示区间

• 区间问题只需要考虑 区间头和区间尾

代码模板

常用于一维区间 DP

for len ∈ [1,N]  		// 长度从小到大
  for i=1,j; (j = i + len -1) && j < N ; i++ // 以 i 为 开头, j 结尾的 区间
    for k ∈ [i, j]  // 以 k 为分割点，进行分治
      // 状态转移方程