Course contentsShow
← Computer Science
Lesson 960 of 2,87222. Dynamic ProgrammingFree lesson

Knuth's Optimization

Exploit quadrangle inequality to optimize certain 2D DP problems from O(n³) to O(n²).

Knuth's Optimization

What You'll Learn

You'll learn how to exploit the quadrangle inequality property to speed up certain 2D DP problems from O(n³) to O(n²).

The Core Idea

Many dynamic programming problems use a formula like:

dp[i][j] = min/max over k of (dp[i][k] + dp[k+1][j] + cost[i][j])

This requires testing every possible split point k between i and j, leading to O(n³) time. Knuth's Optimization notices that when your cost function satisfies the quadrangle inequality, the optimal split point moves monotonically—meaning if the best k for dp[i][j] is 5, then the best k for dp[i][j+1] won't be 2 or 3; it'll be ≥ 5.

Instead of recalculating from scratch, you track:

  • opt[i][j] = the optimal split point for interval [i, j]

Then search only between opt[i][j-1] and opt[i+1][j] when computing dp[i][j].

When Can You Use It?

Your cost function must satisfy the quadrangle inequality: cost[a][c] + cost[b][d] ≤ cost[a][d] + cost[b][c] for all a ≤ b ≤ c ≤ d

Classic example: Matrix Chain Multiplication can use Knuth's Optimization because its cost structure satisfies this property.

Why It Works

The quadrangle inequality ensures that crossing intervals doesn't become cheaper—so the optimal split point can't "jump backwards" as you expand your interval. This monotonicity lets you prune the search space dramatically.

Key Takeaway: Knuth's Optimization reduces O(n³) DP to O(n²) when the cost function satisfies the quadrangle inequality, by exploiting monotonicity of optimal split points.