Higher-level Dynamic Programming——较高级的动态规划 · 区间动规

· · 个人记录

用这道题引出区间DP吧qwq

[蒟蒻的启发式传送门](https://www.luogu.org/problemnew/show/P1063#sub)

define ~区间动规 ~~一维区间动规

一、区间动规的相关

区间动规，说到底也是一位的动态规划，即“线性动态规划”。而最普通的线性动态规划便是一维逻辑关系的动规，即是我们可以由前面推导出来的最优状态推导出当前的最优状态，并且推导的子母顺序大多都是由小到大，或者是某个简单的一维演变次序。

而区间动规的演变次序也是一维的，不过这个一维不同于平常了逻辑上的一维，是由子区间推导出母区间，并具有以下性质（qwq但这些性质好像对于解题没有什么用处）

并不能通过某种空间时间的次序推演出整体最优值。

（比如不能像背包一样从头到尾枚举物品等）

这个所谓的空间时间推演次序看起来好像很阔怕