Pattern Guide
Divide & Conquer DP Optimization
"Reduce O(n²k) DP to O(nk log n) when optimal split point is monotone."
Divide and Conquer DP optimization reduces certain O(n²) DP recurrences to O(n log n) by exploiting the monotone optimal split property: if opt(i) is the optimal split for state i, then opt(i) ≤ opt(i+1). This allows a divide-and-conquer approach: solve the midpoint, recurse on left with opt ≤ opt(mid) and right with opt ≥ opt(mid). Also covers Knuth-Yao speedup for specific interval DP.
Problems you can solve with this pattern
3 problems · click any to start solving
// dp[j] = min over k in [lo, hi] of { prev[k] + cost(k, j) }
// Requires: optimal k for j <= optimal k for j+1 (monotone opt)
function dcDP(prevDP, n, cost) {
const dp = new Array(n).fill(Infinity);
function solve(lo, hi, optLo, optHi) {
if (lo > hi) return;
const mid = (lo + hi) >> 1;
let bestK = optLo, bestVal = Infinity;
// Find optimal k for mid in [optLo, min(optHi, mid)]
for (let k = optLo; k <= Math.min(optHi, mid); k++) {
const val = prevDP[k] + cost(k, mid);
if (val < bestVal) { bestVal = val; bestK = k; }
}
dp[mid] = bestVal;
// Left half: optimal k in [optLo, bestK]
solve(lo, mid - 1, optLo, bestK);
// Right half: optimal k in [bestK, optHi]
solve(mid + 1, hi, bestK, optHi);
}
solve(0, n - 1, 0, n - 1);
return dp;
}
// Knuth-Yao speedup for interval DP:
// dp[i][j] = min(dp[i][k] + dp[k][j] + w(i,j)) for i < k < j
// Requires: opt[i][j-1] <= opt[i][j] <= opt[i+1][j] (quadrangle inequality)
// Reduces O(n³) interval DP to O(n²)DC DP optimization applies when dp[i][j] = min over k of (dp[i-1][k] + cost(k,j)), AND the optimal k for state j (call it opt(j)) satisfies opt(j) ≤ opt(j+1). Instead of trying all n values of k for each j (O(n²)), we solve the middle j first, then recurse on left half with k ≤ opt(mid) and right half with k ≥ opt(mid). Total O(n log n) per DP layer.
// dp[j] = min over k in [lo, hi] of { prev[k] + cost(k, j) }
// Requires: optimal k for j <= optimal k for j+1 (monotone opt)
function dcDP(prevDP, n, cost) {
const dp = new Array(n).fill(Infinity);
function solve(lo, hi, optLo, optHi) {
if (lo > hi) return;
const mid = (lo + hi) >> 1;
let bestK = optLo, bestVal = Infinity;
// Find optimal k for mid in [optLo, min(optHi, mid)]
for (let k = optLo; k <= Math.min(optHi, mid); k++) {
const val = prevDP[k] + cost(k, mid);
if (val < bestVal) { bestVal = val; bestK = k; }
}
dp[mid] = bestVal;
// Left half: optimal k in [optLo, bestK]
solve(lo, mid - 1, optLo, bestK);
// Right half: optimal k in [bestK, optHi]
solve(mid + 1, hi, bestK, optHi);
}
solve(0, n - 1, 0, n - 1);
return dp;
}
// Knuth-Yao speedup for interval DP:
// dp[i][j] = min(dp[i][k] + dp[k][j] + w(i,j)) for i < k < j
// Requires: opt[i][j-1] <= opt[i][j] <= opt[i+1][j] (quadrangle inequality)
// Reduces O(n³) interval DP to O(n²)- dp[j] = min over k of (prev[k] + cost(k, j))
- opt(j) ≤ opt(j+1) where opt(j) = argmin k for state j
- This holds when cost function satisfies the "monotone minima" property
Knuth-Yao conditions: For interval DP dp[i][j] = min(dp[i][k]+dp[k][j]+w[i][j]):
- w satisfies quadrangle inequality: w[a][c]+w[b][d] ≤ w[a][d]+w[b][c] for a≤b≤c≤d
- Then opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]
- Reduces O(n³) to O(n²)
Common applicable problems: k-partition min cost, matrix chain multiplication (Knuth), optimal BST (Knuth), polygon triangulation.