动态规划优化方法大全
动态规划（Dynamic Programming, DP）是算法设计中非常重要的一类方法。在基础DP的基础上，为了提升效率、降低时间或空间复杂度，人们发展出了多种DP优化技术。以下是一份较为全面的动态规划优化方法清单，包括原理简述和典型应用场景。
一、基于状态转移结构的优化
1. 单调队列优化 DP
- 适用场景：形如\[dp[i] = \min_{j < i,\, j \in [L(i), R(i)]} \{ dp[j] + cost(j,i) \} \]其中 \(cost\) 满足某些单调性（如 \(cost\) 与 \(i,j\) 线性相关）。
- 典型问题：滑动窗口最小值、最大子段和带长度限制、任务调度等。
- 时间复杂度：通常从 \(O(n^2)\) 降到 \(O(n)\)。
2. 斜率优化（凸壳优化 / Convex Hull Trick, CHT）
- 适用场景：转移方程可转化为\[dp[i] = \min_{j < i} \{ a_i b_j + c_j \} + d_i \]即关于 \(j\) 的表达式是线性的，且 \(a_i\) 单调。
- 分类：
- 离线 CHT（用单调队列维护下凸/上凸壳）
- 在线 CHT（用平衡树或李超树支持任意顺序查询）
- 典型问题：打印文章（HDU 3507）、玩具装箱（BZOJ 1010）等。
- 时间复杂度：\(O(n)\) 或 \(O(n \log n)\)。
3. 决策单调性优化
- 前提：若对于 \(i_1 < i_2\)，其最优决策点 \(j_1 \leq j_2\)，则称具有决策单调性。
- 实现方式：
- 分治法（Divide and Conquer Optimization）：适用于转移形式为\[dp[i] = \min_{j < i} \{ dp[j] + w(j+1,i) \} \]且 \(w\) 满足四边形不等式。
- 单调栈/队列维护分段决策。
- 分治法（Divide and Conquer Optimization）：适用于转移形式为
- 典型问题：邮局选址、将序列划分为 \(k\) 段使代价最小等。
- 时间复杂度：\(O(n \log n)\) 或 \(O(kn \log n)\)。
4. 四边形不等式优化（Quadrangle Inequality Optimization）
- 条件：若代价函数 \(w(l, r)\) 满足：
- 区间包含单调性：\(w(a, c) \leq w(b, d)\)，当 \(a \leq b \leq c \leq d\)；
- 四边形不等式：\(w(a, d) + w(b, c) \geq w(a, c) + w(b, d)\)（对 \(a \leq b \leq c \leq d\)）。
- 结论：则 DP 的最优决策点具有单调性，可用决策单调性优化。
- 典型问题：石子合并（某些变种）、最优二叉搜索树。
- 注意：常与分治优化结合使用。
二、基于维度压缩或状态表示的优化
5. 滚动数组（Rolling Array）
- 目的：节省空间，将 \(O(nk)\) 空间降为 \(O(k)\)。
- 适用：当前状态仅依赖前一层（如背包、LCS、编辑距离）。
- 注意：需小心遍历顺序（01背包逆序，完全背包正序）。
6. 状态压缩 DP（Bitmask DP）
- 适用：状态可表示为位掩码（如子集、图中顶点选择）。
- 典型问题：旅行商问题（TSP）、铺瓷砖、独立集计数。
- 复杂度：\(O(n \cdot 2^n)\)，适用于 \(n \leq 20\sim25\)。
7. 轮廓线 DP（插头 DP / 基于连通性的状态压缩）
- 思想：逐格推进，用“轮廓线”记录当前行与上一行的连接状态。
- 典型问题：多米诺骨牌覆盖、哈密顿路径计数、网格连通性问题。
- 代表：插头 DP（广义轮廓线 DP）。
三、基于数据结构的优化
8. 线段树 / 树状数组优化 DP
- 适用：转移为\[dp[i] = \min_{j < i,\, cond(j)} \{ dp[j] + f(i,j) \} \]若 \(f(i,j)\) 可拆解为与 \(i\) 相关和与 \(j\) 相关的部分，可用数据结构维护。
- 典型问题：最长上升子序列（LIS）的 \(O(n \log n)\) 解法、带限制的序列划分。
- 扩展：权值线段树、动态开点、离散化配合使用。
9. 李超树（Li-Chao Tree）
- 用途：维护一组直线，支持插入和查询某 \(x\) 处的最小/最大 \(y\) 值。
- 适用：斜率优化中 \(a_i\) 不单调的情况（在线 CHT）。
- 复杂度：\(O(\log U)\) 每次操作（\(U\) 为定义域范围）。
四、基于问题结构的高级优化
10. 倍增优化 DP（Doubling / Sparse Table Style）
- 思想：预处理“跳 \(2^k\) 步”的状态，用于快速回答长距离转移。
- 典型应用：
- 树上 LCA（本质是 DP 倍增）
- 序列上的跳跃游戏（如“跳表式”DP）
- 快速矩阵幂（虽非传统 DP，但思想类似）
- 注意：要求转移具有结合律或可合并性。
11. 矩阵快速幂优化线性递推 DP
- 适用：状态转移为线性递推，如斐波那契、线性齐次递推。
- 方法：将递推关系写成矩阵形式，用快速幂加速。
- 复杂度：\(O(k^3 \log n)\)，\(k\) 为状态维数。
12. 期望 DP 与高斯消元
- 适用：带环的期望 DP（如随机游走），无法直接拓扑排序。
- 方法：列出方程组，用高斯消元求解。
- 优化：若图结构特殊（如链、树），可线性求解。
13. 树形 DP 优化技巧
- 换根 DP（二次扫描）：先 DFS 求子树信息，再 DFS 换根更新全局答案。
- 长链剖分优化：用于优化与深度相关的树形 DP（如 \(k\) 级祖先、特定深度统计），可将 \(O(n^2)\) 降至 \(O(n)\)。
- 虚树优化：当只关心关键点时，压缩树结构加速 DP。
14. 数位 DP 优化
- 记忆化搜索：按位处理，记录是否受限、前导零等状态。
- 优化点：状态设计精简、预处理合法数字组合。
15. CDQ 分治优化 DP
- 思想：将 DP 转移视为三维偏序问题，用分治处理。
- 典型：二维 LIS、带时间顺序的多维限制 DP。
- 复杂度：\(O(n \log^2 n)\)。
16. 闵可夫斯基和 / 凸包合并优化
- 高级技巧：用于多阶段凸函数 DP 的合并（如某些费用流模型）。
- 应用场景较少，但理论强大。
五、其他特殊优化
17. 稀疏表（Sparse Table）辅助 DP
- 用途：快速查询区间最值/和，用于预处理 \(w(l,r)\)。
- 配合：四边形不等式、RMQ 类 DP。
18. meet-in-the-middle 与 DP 结合
- 思想：将问题分成两半，分别 DP 后合并。
- 典型：大容量背包（\(n=40\), \(w=10^9\)）、子集和。
19. 自动机 + DP（AC 自动机 / KMP + DP）
- 用途：字符串匹配约束下的计数 DP。
- 典型：不含某些子串的字符串个数（POI、Codeforces 常见）。
总结表格
\[\begin{array}{|l|l|l|l|}
\hline
\textbf{优化方法} & \textbf{核心思想} & \textbf{典型复杂度} & \textbf{适用问题类型} \\
\hline
\text{单调队列} & \text{维护滑动窗口最值} & O(n) & \text{带窗口限制的 DP} \\
\hline
\text{斜率优化 (CHT)} & \text{线性函数取 min/max} & O(n)\text{ / }O(n \log n) & \text{形如 } dp[j] + a_i b_j \\
\hline
\text{决策单调性 + 分治} & \text{最优决策点单调} & O(n \log n) & \text{区间划分、四边形不等式} \\
\hline
\text{四边形不等式} & \text{保证决策单调性} & \text{配合其他优化} & \text{区间 DP} \\
\hline
\text{滚动数组} & \text{空间复用} & \text{空间 } O(1\sim k) & \text{背包、LCS 等} \\
\hline
\text{状态压缩} & \text{位运算表示状态} & O(n \cdot 2^n) & \text{小规模组合问题} \\
\hline
\text{线段树 / BIT} & \text{动态维护前缀最优值} & O(n \log n) & \text{LIS、带条件转移} \\
\hline
\text{李超树} & \text{动态维护直线集合} & O(n \log U) & \text{非单调斜率优化} \\
\hline
\text{倍增 DP} & \text{预处理 } 2^k \text{ 跳转} & O(n \log n) & \text{树上、序列跳跃} \\
\hline
\text{矩阵快速幂} & \text{线性递推转矩阵} & O(k^3 \log n) & \text{斐波那契类递推} \\
\hline
\text{树形 DP（长链剖分）} & \text{利用长链合并信息} & O(n) & \text{深度相关树形 DP} \\
\hline
\text{CDQ 分治} & \text{分治处理偏序转移} & O(n \log^2 n) & \text{多维限制 DP} \\
\hline
\end{array}
\]
💡 提示：很多优化方法可以组合使用，例如：
- 斜率优化 + 李超树（处理非单调）
- 决策单调性 + 分治 + 四边形不等式
- 树形 DP + 长链剖分 + 换根