动态规划优化方法大全

动态规划优化方法大全

动态规划（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\) 满足四边形不等式。
  • 单调栈/队列维护分段决策。
• 典型问题：邮局选址、将序列划分为 \(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 + 长链剖分 + 换根