动态规划——区间DP 学习笔记
不含四边形不等式优化。
定义
线性动态规划的局限性在于，它只能顺推或倒退，而不能有子区间依赖的问题。
区间动态规划是线性动态规划的扩展，它将问题划分为若干个子区间，并通过定义状态和状态转移方程来求解每个子区间的最优解，最终得到整个区间的最优解。
区间动态规划常用于解决一些涉及区间操作的问题，是一种高效的求解区间最优值的方法，可以有效地解决各种区间问题。
性质
- 子区间可拆分：即能将问题分解为能两两合并的形式；
- 子区间独立性：即将区间 \([l, r]\) 拆分为两个区间后，这两个区间内无论怎么变化，都不应影响到另一区间的最优值；
- 子区间可合并：即能将两个或多个部分进行整合。
求解方法
通常需要定义一个二维状态 \(dp_{i,j}\) 来表示子区间的状态，有时也会根据情况增加维度；常见的 \(i\) 与 \(j\) 的含义有：
- 从第 \(i\) 个物品到第 \(j\) 个物品的最优值；
- 从第 \(i\) 个物品开始，长度为 \(j\) 的区间最优值；
- 前 \(i\) 个物品分为 \(j\) 段时的最优值。
然后对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值；常见的区间拆分方式有：
- \([l, r] \Rightarrow [l, k] + [k + 1, r]\).
- \([l, r] \Rightarrow [l, k - 1] + [k, r]\).
- \([l, r] \Rightarrow [l, k - 1] + [k + 1, r]\).
最重要的是保证拆分的子区间的［可拆分、独立性、可合并］（见上方性质）。
最常见的形式是：令状态 \(f(i,j)\) 表示将下标位置 \(i\) 到 \(j\) 的所有元素合并能获得的价值的最大值，那么 \(f(i,j)=\max\{f(i,k)+f(k+1,j)+\mathrm{cost}\}\)，\(\mathrm{cost}\) 为将这两组元素合并起来的代价。
应用
套路：区间包含的处理
例如：有区间 \(A:[l, r]\) 和 \(B:[a, b]\)，且 \(a \ge l, b \le r\)，即 \(B \subseteq A\)。
则可以考虑先考虑用 \(dp\) 处理其中一类区间，另一类特殊处理。
套路：环的处理
断环为链：从任意位置将环拆解为一条链，并将这条链延长两倍；
新的链长度为 \(2 \times n\) 且第 \(i\) 个元素与第 \(n+i\) 个元素相同；
用动态规划求解后，取 \(f(1,n),f(2,n+1),\dots,f(n-1,2n-2)\) 中的最优值，即为最后的答案。
习题
见：https://www.luogu.com.cn/training/384114文章来源：https://www.toymoban.com/news/detail-710387.html
Reference
[1] https://oi-wiki.org/dp/interval/
[2] https://blog.csdn.net/DUXS11/article/details/131577410文章来源地址https://www.toymoban.com/news/detail-710387.html
到了这里，关于动态规划——区间DP 学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
