核心概述
分治 DP 通过区间二分与跨区合并优化区间/序列类转移，常将 O(n^3) 降至 O(n^2 log n)，具体取决于跨区合并代价与问题结构性质。
原文引述
Description: Optimize interval DP via divide-and-conquer: solve left/right halves recursively, then handle cross contributions. ——来源：本节点英文注释 Time: O(n^2 log n) typical; depends on merge cost ——来源：本节点英文注释 Status: tested ——来源：本节点英文注释 ——摘自本节点现有英文注释 分治 DP（Divide and Conquer DP）：将区间 DP 问题按区间中点分治，先处理子区间，再合并中间跨区间的贡献。典型用于区间 DP、路径计数、树形 DP 的优化，复杂度常从 O(n^3) 降至 O(n^2 log n)。
展开阐述
-
概览：分治 DP（Divide and Conquer DP）将区间 DP 按中点递归，并在每层合并跨区贡献，典型可将 O(n^3) 降至 O(n^2 log n)，具体取决于跨区合并代价与问题结构性质。
-
典型问题模型
- DP[l][r] 表示区间 [l,r] 的答案。
- 转移形如：DP[l][r] = min_{k∈[l,r)} (DP[l][k] + DP[k][r] + cost(l,k,r))。
- 若 cost(l,k,r) 可表示为 f(l) + g(k) + h(r) 等可分离形式，则能用分治优化。
-
分治算法步骤
- solve(l, r)：
- 若 r−l ≤ 1（区间长度 0/1），直接计算。
- 中点 m = (l+r)/2。
- 先递归 solve(l, m) 与 solve(m, r)。
- 处理跨区贡献：
- 对每个 i∈[l,m]，求最优 j∈[m,r) 使得 DP[l][i] + DP[i][r] + cost(l,i,r)。
- 利用凸性/单调性，用双指针/三分在 O(n) 内计算所有 i 的最优 j。
- 返回 DP[l][r]。
- solve(l, r)：
-
优化前提
- 决策单调性：若对 i1<i2，最优决策点 j1≤j2，则可用双指针维护。
- 四边形不等式：cost 具有子模性，可保证决策点单调。
- 凸性/凹性：cost 关于决策点凸，可用三分或凸优化。
-
经典应用
- 区间 DP：石子合并、矩阵链乘、括号匹配等。
- 路径计数：固定起点的最短路计数。
- 树形 DP：树上的路径优化问题（重链剖分配合）。
-
实现技巧
- 每层递归处理跨区时，可预计算前缀/后缀信息，降低合并成本。
- 用记忆化避免重复计算子区间。
- 注意边界与递归深度，防止栈溢出。
-
复杂度分析
- 递归深度 O(log n)，每层处理跨区 O(n)，总计 O(n log n)。
- 若合并需 O(n) 内枚举，总 O(n^2 log n)；更优合并可达 O(n log n)。
-
使用与注意
- 先检验 DP 是否满足决策单调或四边形不等式。
- 对小区间可设阈值直接暴力处理，降低常数。
- 与 136-杂项-Knuth优化DP 对比：Knuth 优化用于 O(n^2) 单调决策，分治用于 O(n^2 log n) 场景。