区间DP($O(n^3)$)
到目前为止,我们介绍的线性DP一般从初态开始,沿着阶段的扩张向某个方向递推,直至计算出目标状态。区间DP也属于线性DP中的一种,它以“区间长度”作为DP的“阶段”,使用两个坐标(区间的左、右端点)描述每个维度。在区间DP中,一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来,因此区间DP的决策往往就是划分区间的方法。区间DP的初态一般就由长度为1的“元区间”构成。这种向下划分、再向上递推的模式与某些树形结构,例如第0x43节的线段树,有很大的相似之处。我们把区间DP作为线性DP中一类重要的分支单独进行讲解,将使读者更容易理解下一节树形DP的内容。同时,借助区间DP这种与树形相关的结构,我们也将提及记忆化搜索——其本质是动态规划的递归实现方法。
for 区间长度:
for 左端点:
得到右端点
#最后一步/for 分界点
状态转移
佬,方便问一下这段话出自哪里吗
李煜东的《算法竞赛进阶指南》
好的,谢谢!