动态规划——区间DP 学习笔记

动态规划——区间DP 学习笔记

不含四边形不等式优化。

定义

线性动态规划的局限性在于,它只能顺推或倒退,而不能有子区间依赖的问题。

区间动态规划是线性动态规划的扩展,它将问题划分为若干个子区间,并通过定义状态和状态转移方程来求解每个子区间的最优解,最终得到整个区间的最优解。

区间动态规划常用于解决一些涉及区间操作的问题,是一种高效的求解区间最优值的方法,可以有效地解决各种区间问题。

性质

  1. 子区间可拆分:即能将问题分解为能两两合并的形式;
  2. 子区间独立性:即将区间 \([l, r]\) 拆分为两个区间后,这两个区间内无论怎么变化,都不应影响到另一区间的最优值;
  3. 子区间可合并:即能将两个或多个部分进行整合。

求解方法

通常需要定义一个二维状态 \(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}\) 为将这两组元素合并起来的代价。

应用

套路:环的处理

断环为链:从任意位置将环拆解为一条链,并将这条链延长两倍;

新的链长度为 \(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

Reference

[1] https://oi-wiki.org/dp/interval/
[2] https://blog.csdn.net/DUXS11/article/details/131577410

热门相关:落地一把98K   重生成偏执霍少的小仙女   一等狂妃:邪王,请接招!   重生之将门毒后   悠哉兽世:种种田,生生崽