DP 优化简介
引入
本页面列举了一些常见的动态规划(dynamic programming,DP)优化方法。所谓 DP 优化,是指许多动态规划问题虽然容易列出朴素的状态转移方程,但直接计算往往效率低下,因此需要借助一些技巧来降低时间复杂度。
这些方法彼此联系紧密,常常包含相似的思想,且往往需要结合多种技巧共同使用。因此,本文仅作粗略分类,侧重介绍一些最基本的思路。
利用常见技巧优化
许多动态规划问题的转移,可以通过常见的算法和数据结构进行优化。
这类技巧有两种常见的情形。第一种情形中,DP 问题有着如下状态转移方程:
其中,当前状态
第二种情形中,DP 问题有着如下状态转移方程:
其中,每个
前缀和优化 DP
相关页面:前缀和
如果当前状态的计算依赖于之前状态的子段和,那么,可以通过维护前缀和来加速计算。其中,涉及高维前缀和的问题也称为 SOS DP。
习题:
单调队列/单调栈优化 DP
主页面:单调队列/单调栈优化
如果当前状态依赖于之前状态的区间最值等信息时,可以通过维护单调队列、单调栈来加速计算。
线段树/树状数组优化 DP
如果每次状态转移时,查询的都是某段区间上的和、最值等信息,或是单次修改操作涉及区间更新时,可以通过维护线段树、树状数组来加速计算。
习题:
- AtCoder Educational DP Contest Q - Flowers
- AtCoder Educational DP Contest W - Intervals
- Codeforces 115 E. Linear Kingdom Races
CDQ 分治优化 DP
主页面:CDQ 分治优化 DP
类似前文,将整个 DP 过程看作是一系列查询和修改操作。对于有些问题,顺次计算复杂度过高,可以将整个查询和修改过程离线,利用 CDQ 分治加速计算。
CDQ 分治优化 DP 也常见于下列各类问题中:
倍增优化 DP
相关页面:倍增
有些问题中,需要将状态
有些时候,也会将状态转移方程类似
的 DP 问题称为倍增(优化)DP。
习题:
利用问题结构优化
许多动态规划问题具备如凸性、单调性等结构性质,合理利用这些性质可以快速求解。
斜率优化 DP
主页面:斜率优化
类似于上一节介绍的优化方法,利用问题的凸性,可以通过维护凸包加速单次转移。
四边形不等式优化 DP
主页面:四边形不等式优化
涉及的函数满足四边形不等式的 DP 问题,往往满足某种决策单调性。利用这一特性,有很多专门的方法可以降低计算复杂度。常见的问题类型包括一维决策单调性问题、区间分拆问题、区间合并问题等。
Slope Trick 优化 DP
主页面:Slope Trick
有些问题中,状态函数的差分(即斜率)在状态转移过程中更容易维护。这种优化也往往需要问题具有凸性。
WQS 二分/凸优化 DP
主页面:WQS 二分
对于带个数限制的最优化 DP 问题,如果不考虑个数限制时,问题更容易解决,且最优价值是关于该限制的凸函数,那么,可以通过 WQS 二分的方法简化计算。
利用数学方法优化
许多动态规划问题的转移,可以通过数学工具加速。
矩阵快速幂优化 DP
相关页面:快速幂
如果 DP 问题的状态转移方程可以写作一个自治的形式
也就是说,当前状态
获得最终答案。由于单次操作
习题:
- Luogu P1397 [NOI2013] 矩阵游戏
- Luogu P3176 [HAOI2015] 数字串拆分
- Codeforces 576 D. Flights for Regular Customers
- Luogu P6772 [NOI2020] 美食家
FFT 优化 DP
相关页面:FFT
如果 DP 问题的状态转移方程是一个卷积的形式,那么,可以考虑用 FFT 加速转移。当然,根据具体的题目,也可能会用到其他多项式技术。
习题:
Lagrange 插值优化 DP
相关页面:Lagrange 插值
有些 DP 问题的状态函数
习题:
通过简化状态优化
除了优化转移外,还可以通过简化状态降低计算复杂度。
DP 套 DP 与 DFA 最小化
一些 DP 问题的状态函数可以写成
状态设计优化 DP
主页面:状态设计优化
有些特殊的问题可以通过巧妙的状态设计大幅减少状态数量。
拓展阅读
本页面最近更新:2025/8/5 18:12:34,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:c-forrest, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用