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

用这道题引出区间$DP$吧$qwq$ _[蒟蒻的启发式传送门]_(https://www.luogu.org/problemnew/show/P1063#sub) #$define$ $~$区间动规 $~~$一维区间动规 ## 一、区间动规的相关 区间动规，说到底也是一位的动态规划，即“线性动态规划”。而最普通的线性动态规划便是一维逻辑关系的动规，即是我们可以由前面推导出来的最优状态推导出当前的最优状态，并且推导的子母顺序大多都是由小到大，或者是某个简单的一维演变次序。 而区间动规的演变次序也是一维的，不过这个一维不同于平常了逻辑上的一维，是由子区间推导出母区间，并具有以下性质（$qwq$但这些性质好像对于解题没有什么用处） ### 并不能通过某种空间时间的次序推演出整体最优值。 （比如不能像背包一样从头到尾枚举物品等） 这个所谓的空间时间推演次序看起来好像很阔怕