Applicability

The divide and conquer optimization applies when the dynamic programming recurrence is approximately of the form

where $A[k][i] \leq A[k][i+1]$. Here $A[k][i]$ is the smallest index $j^\star < i$ that minimizes $\mathrm{dp}[k-1][j^\star] + C[i][j^\star]$, i.e.

A sufficient (but not necessary) condition for $A[k][i] \leq A[k][i+1]$ to hold is that $C[a][c] + C[b][d] \leq C[a][d] + C[b][c]$ where $a < b < c < d$

The naive way of computing this recurrence with dynamic programming takes $O(kn^2)$ time, but only takes $O(kn\log n)$ time with the divide and conquer optimization.

Problems

• Guardians of the Lunatics¹
• Branch Assignment
• Mining
• Ciel and Gondolas²
• Leaves

See also

• Dynamic programming optimization
• Divide and conquer

External links

• Dynamic Programming Optimizations