分治优化决策单调DP
当 Q_(i,j) (f(j))=w(i,j) 与 f(j) 无关且最优决策点满足决策单调性时,按中点扫描候选区间并递归,以 O(n log n) 求出全部 f(i)。时间 O(n log n),空间 O(n) · 标签 动态规划 / 决策单调性 / 分治 / DP 优化
问题形式
考虑 1D/1D 动态规划中,当 与 无关,且最优决策点满足 决策单调性 时,方程退化为
其中 。因为 不含 , 的值不受其他 的影响,计算顺序可以任意;转移范围仍按 的定义。
核心思想
记 计算 ,并已知这些状态的最优决策都在 。
取 ,在 中扫描,求出 ,再计算
递归计算 和 。初始调用为 。
分治树每层扫描的候选区间总长为 ,共 层,因此总时间为 。
正确性
分治的不变式是:进入 时,任意 的 都在 内。
取 后,扫描范围包含 与 的交,因此能找到 。由 单调,左半部分满足 ,右半部分满足 ,递归范围正确。
由于 与 无关,计算 不需要左侧的 ,所以可以先算 再递归。归纳得所有 正确。
易错点
- 依赖 时不能用本页分治:计算 时,左侧的 可能尚未计算。
- 扫描范围要取 与 的交,不能漏掉端点。
- 分治是 ,不是 ;每层都要扫描候选。