分治优化（Divide and Conquer Optimization）是一种用于加速特定类型动态规划（DP）的技巧：当 DP 的转移满足一定的“最优决策点单调性”等条件时，可以用分治思想把求解范围递归地切开，把原本常见的 \(O(n^2)\)（或更高）转移降低到通常的 \(O(n \log n)\) 或 \(O(k n \log n)\)（取决于维度与实现）。
（该术语在算法竞赛与算法工程中更常见；不同资料对适用条件的表述略有差异。）
/ˌdɪˈvaɪd ænd ˈkɑːŋkər ˌɑːptɪməˈzeɪʃən/
Divide and conquer optimization can make this DP fast enough to pass.
分治优化可以让这个动态规划快到足以通过。
When the cost function has the right structure, divide and conquer optimization reduces the transition from quadratic time to near-linear per layer.
当代价函数具备合适的结构时，分治优化能把转移从二次时间降低到每一层接近线性的复杂度。
divide and conquer 源自经典策略思想，字面义为“分而治之/各个击破”，在计算机科学中常指把问题拆成规模更小的子问题递归解决（如归并排序）。optimization 来自“优化”。合在一起，这个短语在算法语境中特指：用分治来“优化”某类 DP 的计算过程，因此也常被称为 分治 DP 优化。
Select Language