Applicability

Knuth's optimization applies when the dynamic programming recurrence is approximately of the form

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

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

The naive way of computing this recurrence with dynamic programming takes $O(n^3)$ time, but only takes $O(n^2)$ time with Knuth's optimization.

Problems

• Optimal Binary Search Tree
• Guardians of the Lunatics¹
• Order-Preserving Codes
• Breaking Strings

See also

• Dynamic programming optimization

External links

• Dynamic Programming Optimizations
• ZOJ 2860 Breaking Strings
• Commonly used DP state domains