dp 标签归档 | 土法炼钢兴趣小组的算法知识备份

树形 DP：换根、虚树与树上背包

树形 DP 是动态规划中最优美的分支之一。换根技巧将复杂度从 O(n^2) 降到 O(n)，虚树将多次查询的总复杂度压缩到关键点规模。

当问题的状态空间是集合的幂集时，位运算提供了优雅的压缩表示。从 TSP 到 SOS，状压 DP 是处理 NP-hard 问题精确解的核心武器。

当 DP 转移方程可以写成线性形式，凸包技巧将 O(n^2) 优化到 O(n log n) 甚至 O(n)。这是竞赛和工业优化中最强大的 DP 加速手段之一。

当 DP 的最优决策点具有单调性时，分治技巧可以将 O(n^2) 优化到 O(n log n)。四边形不等式是识别这种结构的关键数学工具。

区间 DP 是处理'在区间上做最优决策'问题的通用框架。从矩阵链乘到 RNA 折叠，它的应用远比教科书展示的更广泛。

动态规划不只是算法竞赛的工具。从广告预算分配到 GPS 轨迹匹配，DP 的思想在工业系统中以各种形式默默运行着。