Divide-and-Conquer DP 发音

释义 Definition

Divide-and-Conquer DP（分治优化动态规划）：一种用于加速某些动态规划（DP）转移的技巧。它利用“最优决策点（argmin/argmax）具有单调性”等性质，把每一层 DP 的计算用分治方式完成，从而把时间复杂度常见地从 O(kn) 降到 **O(knlog n)**（或相近量级）。常见于区间划分、分组最优化等问题。

注：它通常特指 Divide and Conquer Optimization（分治优化），是 DP 优化套路之一。

发音 Pronunciation (IPA)

/dvad n kkr di pi/

例句 Examples

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)\)。

词源 Etymology

“divide-and-conquer”意是“分而治之”，早用于军事与政治策略（把问题拆分、分别解决）；在计算机科学中指一类经典算法思想（如归并排序）。
“DP”是 dynamic programming（动态规划） 的缩写。合在一起的 “divide-and-conquer DP” 则是把“分治”的结构用于加速某些 DP 的计算，因此中文常译为“分治优化 DP/分治 DP 优化”。

相关词 Related Words

• Dynamic-Programming
• Optimization
• Divide-And-Conquer
• Monotonicity
• Argmin
• Convex-Hull-Trick
• Knuth-Optimization
• Prefix-Sum

文献与作品 Literary / Notable Works

• Competitive Programming 4（Steven Halim 等）：在 DP 优化章节中常讨论分治优化思想与应用场景。
• *Introduction to Algorithms (CLRS)*：系统介绍分治与动态规划两大范式，为理解该技巧提供基础框架。
• Algorithms（Dasgupta, Papadimitriou, Vazirani）：讲解分治与 DP 的核心思想，常被用作相关优化的入门背景读物。