Divide-and-Conquer DP（分治优化动态规划）：一种用于加速某些动态规划（DP）转移的技巧。它利用“最优决策点（argmin/argmax）具有单调性”等性质，把每一层 DP 的计算用分治方式完成，从而把时间复杂度常见地从 O(k·n²) 降到 **O(k·n·log n)**（或相近量级）。常见于区间划分、分组最优化等问题。
注：它通常特指 Divide and Conquer Optimization（分治优化），是 DP 优化套路之一。
/ˈdɪvaɪd ən ˈkɑːŋkər ˌdiː ˈpiː/
We used divide-and-conquer DP to speed up the transition.
我们用分治优化 DP 来加速状态转移。
If the optimal partition point is monotonic, divide-and-conquer DP can reduce the runtime from \(O(n^2)\) to about \(O(n\log n)\) per layer.
如果最优分割点满足单调性，分治优化 DP 往往能把每一层的运行时间从 \(O(n^2)\) 降到约 \(O(n\log n)\)。
“divide-and-conquer”原意是“分而治之”，早用于军事与政治策略（把问题拆分、分别解决）；在计算机科学中指一类经典算法思想（如归并排序）。
“DP”是 dynamic programming（动态规划） 的缩写。合在一起的 “divide-and-conquer DP” 则是把“分治”的结构用于加速某些 DP 的计算，因此中文常译为“分治优化 DP/分治 DP 优化”。
Select Language