AntInLoop

Knuth's DP Optimization

Knuth's Optimization accelerates interval DP recurrences dp[l][r] = min(dp[l][k] + dp[k+1][r]) + cost(l, r) from O(n^3) to O(n^2) whenever the cost satisfies the quadrangle inequality and monotonicity.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Knuth's DP Optimization

Many Interval DP problems (such as Optimal Binary Search Tree and Merging Adjacent Stones) have the form:

$dp[l][r] = \min_{l \le k < r} \Big( dp[l][k] + dp[k + 1][r] \Big) + C(l, r)$

Naively this takes $O(n^3)$. Knuth's Optimization proves that whenever $C(l, r)$ satisfies the Quadrangle Inequality ($C(a, c) + C(b, d) \le C(a, d) + C(b, c)$) and Monotonicity ($C(b, c) \le C(a, d)$ for $a \le b \le c \le d$), the optimal split point opt[l][r] is monotonic:

$\text{opt}[l][r - 1] \le \text{opt}[l][r] \le \text{opt}[l + 1][r]$

Restricting the inner loop k to [opt[l][r - 1], opt[l + 1][r]] telescopes the total work across each diagonal to $O(n)$, cutting total time from $O(n^3)$ to $O(n^2)$!

Practice Problems

Hard

1. Optimal Merging of Adjacent Stones in $O(n^2)$ (Knuth's Optimization)

Given $n$ piles of stones in a row, repeatedly merge two adjacent piles at cost equal to their combined weight until 1 pile remains. Minimize total cost in $O(n^2)$ time!

Approach: C(l, r) = sum(a[l..r]) satisfies the quadrangle inequality (with equality!), so opt[l][r] is bounded by [opt[l][r - 1], opt[l + 1][r]]. Time: $O(n^2)$. Space: $O(n^2)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <limits>
#include <vector>

long long minMergeCostKnuth(const std::vector<long long>& a) {
    int n = static_cast<int>(a.size());
    std::vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];

    const long long INF = std::numeric_limits<long long>::max() / 4;
    std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, 0));
    std::vector<std::vector<int>> opt(n, std::vector<int>(n, 0));
    for (int i = 0; i < n; ++i) opt[i][i] = i;

    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len - 1 < n; ++l) {
            int r = l + len - 1;
            dp[l][r] = INF;
            int lo = opt[l][r - 1], hi = std::min(r - 1, opt[l + 1][r]);
            long long segSum = pref[r + 1] - pref[l];
            for (int k = lo; k <= hi; ++k) {
                long long cand = dp[l][k] + dp[k + 1][r] + segSum;
                if (cand < dp[l][r]) {
                    dp[l][r] = cand;
                    opt[l][r] = k;
                }
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    std::cout << minMergeCostKnuth({1, 3, 5, 2}) << "\n"; // 22
    return 0;
}

</details>

---

Related Algorithms