DP Optimization: Monotonic Queue, Divide-and-Conquer & Knuth's Trick

1. Introduction & Motivation

Many dynamic programming recurrences share the same shape: dp[i] = min over j < i of (dp[j] + cost(j, i)). Computed naively, this recurrence costs $O(n^2)$ time for a single DP layer, or $O(n^3)$ once it also ranges over a second dimension, such as an interval DP with an inner split point. Neither bound is acceptable once $n$ reaches the tens of thousands.

This lesson covers three independent techniques that each accelerate this same recurrence shape by exploiting a different structural property of cost(j, i):

• Monotonic queue optimization exploits a sliding transition window: only the most recent $k$ values of $j$ are ever valid, so a monotonic deque tracks the running best $dp[j]$ in amortized $O(1)$ per step.
• Divide-and-conquer DP optimization exploits monotonicity of the optimal split point: if the best $j$ for a larger $i$ is never smaller than the best $j$ for a smaller $i$, one recursive pass finds every optimal split in $O(n \log n)$ instead of $O(n^2)$.
• Knuth's optimization exploits the quadrangle inequality in interval DP: the optimal split point for a wider interval is sandwiched between the optimal split points of two overlapping narrower intervals, cutting total work from $O(n^3)$ to $O(n^2)$.

None of the three techniques changes what the DP computes — only how fast it computes it. Each one requires proving that the cost function has the necessary structural property before applying it; blindly applying any of them to a recurrence that lacks the property produces wrong answers, not just missed savings.

2. Prerequisites

You should be comfortable defining DP state and deriving a recurrence, as covered in Part 14: Dynamic Programming Foundations — this lesson assumes you can already read dp[i] = min over j of (...) notation and reason about state transitions.

You should also already know how a monotonic deque maintains a sliding-window extremum in amortized $O(1)$ per element; that mechanism — pop dominated candidates from the back, pop stale candidates from the front — is covered in full, including its correctness proof, in Monotonic Deque for Sliding Window Maximum. This lesson does not re-derive that mechanism; it reuses it as-is and applies it to a DP transition instead of a raw array window.

3. Monotonic Queue DP Optimization: Sliding Transition Window

The window is the whole reason this technique differs from a plain sliding-window maximum over raw array values: the values being compared are DP values computed on the fly, one index at a time, and the window's right edge advances in lockstep with the DP loop itself. The deque mechanics — decreasing order of value, pop the back on domination, pop the front on staleness — are exactly those already proved correct in the monotonic deque lesson; the only new part is that the values being pushed are dp[i], computed one step ahead of being pushed.

Constrained Subsequence Sum (LeetCode 1425) is a clean example: given an integer array nums and an integer $k$, choose a non-empty subsequence maximizing its sum, subject to the constraint that any two consecutive chosen indices differ by at most $k$. The recurrence is:

$$dp[i] = nums[i] + \max\left(0,\ \max_{i-k \le j \le i-1} dp[j]\right)$$

Taking $\max(\cdot, 0)$ means "start a fresh subsequence at $i$ if every reachable predecessor would only shrink the sum." The answer is $\max_i dp[i]$. The inner maximum ranges over a window of size $k$, so a monotonic deque of indices — ordered so that dp at those indices is strictly decreasing — gives the window maximum at its front in $O(1)$, for total time $O(n)$ instead of $O(nk)$.

from collections import deque

def constrained_subsequence_sum(nums, k):
    if not nums or k <= 0:
        raise ValueError("nums must be non-empty and k must be positive")
    n = len(nums)
    dp = [0] * n
    dq = deque()  # indices, dp[dq] strictly decreasing
    best_sum = float("-inf")
    for i in range(n):
        while dq and dq[0] < i - k:
            dq.popleft()
        window_best = dp[dq[0]] if dq else 0
        dp[i] = nums[i] + max(window_best, 0)
        best_sum = max(best_sum, dp[i])
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return best_sum

sample = [10, 2, -10, 5, 20]
print("Max constrained subsequence sum:", constrained_subsequence_sum(sample, 2))  # 37

#include <algorithm>
#include <deque>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

long long constrainedSubsequenceSum(const std::vector<int>& nums, int k) {
    if (nums.empty() || k <= 0) {
        throw std::invalid_argument("nums must be non-empty and k must be positive");
    }
    int n = static_cast<int>(nums.size());
    std::vector<long long> dp(n);
    std::deque<int> dq;  // indices, dp[dq] strictly decreasing
    long long bestSum = std::numeric_limits<long long>::min();
    for (int i = 0; i < n; ++i) {
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }
        long long windowBest = dq.empty() ? 0 : dp[dq.front()];
        dp[i] = nums[i] + std::max(windowBest, 0LL);
        bestSum = std::max(bestSum, dp[i]);
        while (!dq.empty() && dp[dq.back()] <= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    return bestSum;
}

int main() {
    std::vector<int> sample{10, 2, -10, 5, 20};
    std::cout << "Max constrained subsequence sum: " << constrainedSubsequenceSum(sample, 2) << '\n';  // 37
}

import java.util.ArrayDeque;
import java.util.Deque;

public class ConstrainedSubsequenceSum {
    static long constrainedSubsequenceSum(int[] nums, int k) {
        if (nums.length == 0 || k <= 0) {
            throw new IllegalArgumentException("nums must be non-empty and k must be positive");
        }
        int n = nums.length;
        long[] dp = new long[n];
        Deque<Integer> dq = new ArrayDeque<>();  // indices, dp[dq] strictly decreasing
        long bestSum = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k) {
                dq.pollFirst();
            }
            long windowBest = dq.isEmpty() ? 0 : dp[dq.peekFirst()];
            dp[i] = nums[i] + Math.max(windowBest, 0L);
            bestSum = Math.max(bestSum, dp[i]);
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
        }
        return bestSum;
    }

    public static void main(String[] args) {
        int[] sample = {10, 2, -10, 5, 20};
        System.out.println("Max constrained subsequence sum: " + constrainedSubsequenceSum(sample, 2)); // 37
    }
}

Tracing the deque on nums = [10, 2, -10, 5, 20], $k=2$: dp = [10, 12, 2, 17, 37]. Index 0 is discarded once its dp value (10) is dominated by index 1's value (12); indices 1 and 2 are discarded once index 3's value (17) dominates them; the deque finally reports dp[4] = 37 as the answer, matching the subsequence 10, 2, 5, 20.

4. A Concrete Example for D&C Optimization

5. Divide-and-Conquer DP Optimization: Monotone Optimal Split Points

The recursive template, applied to the group-partitioning example above, is: compute(lo, hi, optLo, optHi) solves $dp[k][i]$ for every $i$ in [lo, hi], restricting candidate split points to [optLo, optHi]. It picks mid = (lo + hi) / 2, scans only j in [optLo, min(mid-1, optHi)] to find mid's true optimal split bestJ, then recurses on [lo, mid-1] with the upper bound tightened to bestJ and on [mid+1, hi] with the lower bound tightened to bestJ. Because mid's optimal split can never be worse (further left) than the optimal split of anything strictly to its right, and never worse (further right) than the optimal split of anything strictly to its left — that is exactly what monotonicity guarantees — neither recursive half ever needs to look outside its restricted range for the true optimum. Each level of the recursion scans $O(n)$ candidates total across all its calls, and there are $O(\log n)$ levels, giving $O(n \log n)$ per layer $k$.

import math

def min_cost_k_groups(nums, k):
    """Partition nums into k contiguous groups minimizing the sum of squared group sums."""
    n = len(nums)
    if k <= 0 or k > n:
        raise ValueError("k must be between 1 and len(nums)")
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    def cost(j, i):  # cost of grouping elements j+1..i together
        total = prefix[i] - prefix[j]
        return total * total

    INF = math.inf
    dp_prev = [INF] * (n + 1)
    for i in range(1, n + 1):
        dp_prev[i] = cost(0, i)  # k = 1: a single group from the start

    for group in range(2, k + 1):
        dp_cur = [INF] * (n + 1)

        def compute(lo, hi, opt_lo, opt_hi):
            if lo > hi:
                return
            mid = (lo + hi) // 2
            best_cost, best_j = INF, -1
            for j in range(opt_lo, min(mid - 1, opt_hi) + 1):
                candidate = dp_prev[j] + cost(j, mid)
                if candidate < best_cost:
                    best_cost, best_j = candidate, j
            dp_cur[mid] = best_cost
            compute(lo, mid - 1, opt_lo, best_j)
            compute(mid + 1, hi, best_j, opt_hi)

        compute(group, n, group - 1, n - 1)
        dp_prev = dp_cur

    return dp_prev[n]

sample = [1, 2, 3, 6]
print("Minimum cost for 2 groups:", min_cost_k_groups(sample, 2))  # 72

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

// Partition nums into k contiguous groups minimizing the sum of squared group sums.
long long minCostKGroups(const std::vector<int>& nums, int k) {
    int n = static_cast<int>(nums.size());
    if (k <= 0 || k > n) {
        throw std::invalid_argument("k must be between 1 and nums.size()");
    }
    std::vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + nums[i];

    auto cost = [&](int j, int i) {  // cost of grouping elements j+1..i together
        long long total = prefix[i] - prefix[j];
        return total * total;
    };

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

    for (int group = 2; group <= k; ++group) {
        std::vector<long long> dpCur(n + 1, INF);
        std::function<void(int, int, int, int)> compute = [&](int lo, int hi, int optLo, int optHi) {
            if (lo > hi) return;
            int mid = (lo + hi) / 2;
            long long bestCost = INF;
            int bestJ = -1;
            for (int j = optLo; j <= std::min(mid - 1, optHi); ++j) {
                long long candidate = dpPrev[j] + cost(j, mid);
                if (candidate < bestCost) {
                    bestCost = candidate;
                    bestJ = j;
                }
            }
            dpCur[mid] = bestCost;
            compute(lo, mid - 1, optLo, bestJ);
            compute(mid + 1, hi, bestJ, optHi);
        };
        compute(group, n, group - 1, n - 1);
        dpPrev = dpCur;
    }
    return dpPrev[n];
}

int main() {
    std::vector<int> sample{1, 2, 3, 6};
    std::cout << "Minimum cost for 2 groups: " << minCostKGroups(sample, 2) << '\n';  // 72
}

import java.util.Arrays;

public class DivideConquerGroupCost {
    static long[] prefix;
    static long[] dpPrev;
    static long[] dpCur;
    static final long INF = Long.MAX_VALUE / 4;

    static long cost(int j, int i) {  // cost of grouping elements j+1..i together
        long total = prefix[i] - prefix[j];
        return total * total;
    }

    static void compute(int lo, int hi, int optLo, int optHi) {
        if (lo > hi) return;
        int mid = (lo + hi) / 2;
        long bestCost = INF;
        int bestJ = -1;
        for (int j = optLo; j <= Math.min(mid - 1, optHi); j++) {
            long candidate = dpPrev[j] + cost(j, mid);
            if (candidate < bestCost) {
                bestCost = candidate;
                bestJ = j;
            }
        }
        dpCur[mid] = bestCost;
        compute(lo, mid - 1, optLo, bestJ);
        compute(mid + 1, hi, bestJ, optHi);
    }

    // Partition nums into k contiguous groups minimizing the sum of squared group sums.
    static long minCostKGroups(int[] nums, int k) {
        int n = nums.length;
        if (k <= 0 || k > n) {
            throw new IllegalArgumentException("k must be between 1 and nums.length");
        }
        prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

        dpPrev = new long[n + 1];
        Arrays.fill(dpPrev, INF);
        for (int i = 1; i <= n; i++) dpPrev[i] = cost(0, i);  // k = 1

        for (int group = 2; group <= k; group++) {
            dpCur = new long[n + 1];
            Arrays.fill(dpCur, INF);
            compute(group, n, group - 1, n - 1);
            dpPrev = dpCur;
        }
        return dpPrev[n];
    }

    public static void main(String[] args) {
        int[] sample = {1, 2, 3, 6};
        System.out.println("Minimum cost for 2 groups: " + minCostKGroups(sample, 2)); // 72
    }
}

Running this on the same [1, 2, 3, 6] input for $k=2$ groups reproduces the worked example exactly: the recursion computes $i=3$ first (the midpoint of [2,4]), discovers $opt[3]=2$, then restricts the right half's search for $i=4$ to $j \ge 2$ and the left half's search for $i=2$ to $j \le 2$ — both consistent with the table above, and both cheaper than rescanning every $j$ before $i$ again.

6. Knuth's Optimization: The Quadrangle Inequality

The bound is applied cell by cell while filling the DP table by increasing interval length. Since $opt[i][j-1]$ and $opt[i+1][j]$ are both already computed by the time $dp[i][j]$ is processed (they belong to shorter intervals), every cell's search range shrinks to whatever lies between two previously-discovered split points — often just one or two candidates in practice, even though the worst case is still bounded generously enough to guarantee $O(n^2)$ overall, because the total width of all search ranges across a fixed diagonal telescopes to $O(n)$.

Applied to Matrix Chain Multiplication — a dims array p where matrix $i$ is $p[i-1] \times p[i]$, and $dp[i][j]$ is the minimum scalar multiplications to fully parenthesize matrices $i \ldots j$ — the implementation below fills dp by increasing interval length and reuses the opt table to bound each cell's inner loop:

import math

def matrix_chain_knuth(dims):
    """Minimum scalar multiplications to parenthesize a chain of matrices, via Knuth's optimization."""
    n = len(dims) - 1  # number of matrices
    if n < 1:
        raise ValueError("dims must describe at least one matrix")
    INF = math.inf
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    opt = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        opt[i][i] = i

    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            low_k = opt[i][j - 1]
            high_k = min(opt[i + 1][j], j - 1)
            best_cost, best_k = INF, low_k
            for k in range(low_k, high_k + 1):
                candidate = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if candidate < best_cost:
                    best_cost, best_k = candidate, k
            dp[i][j] = best_cost
            opt[i][j] = best_k

    return dp[1][n]

sample_dims = [10, 20, 30, 40, 30]  # 4 matrices: 10x20, 20x30, 30x40, 40x30
print("Minimum multiplication cost:", matrix_chain_knuth(sample_dims))  # 30000

#include <algorithm>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

// Minimum scalar multiplications to parenthesize a chain of matrices, via Knuth's optimization.
long long matrixChainKnuth(const std::vector<long long>& dims) {
    int n = static_cast<int>(dims.size()) - 1;  // number of matrices
    if (n < 1) {
        throw std::invalid_argument("dims must describe at least one matrix");
    }
    const long long INF = std::numeric_limits<long long>::max() / 4;
    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(n + 1, 0));
    std::vector<std::vector<int>> opt(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) opt[i][i] = i;

    for (int length = 2; length <= n; ++length) {
        for (int i = 1; i <= n - length + 1; ++i) {
            int j = i + length - 1;
            int lowK = opt[i][j - 1];
            int highK = std::min(opt[i + 1][j], j - 1);
            long long bestCost = INF;
            int bestK = lowK;
            for (int k = lowK; k <= highK; ++k) {
                long long candidate = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
                if (candidate < bestCost) {
                    bestCost = candidate;
                    bestK = k;
                }
            }
            dp[i][j] = bestCost;
            opt[i][j] = bestK;
        }
    }
    return dp[1][n];
}

int main() {
    std::vector<long long> sampleDims{10, 20, 30, 40, 30};  // 4 matrices
    std::cout << "Minimum multiplication cost: " << matrixChainKnuth(sampleDims) << '\n';  // 30000
}

public class MatrixChainKnuth {
    // Minimum scalar multiplications to parenthesize a chain of matrices, via Knuth's optimization.
    static long matrixChainKnuth(long[] dims) {
        int n = dims.length - 1;  // number of matrices
        if (n < 1) {
            throw new IllegalArgumentException("dims must describe at least one matrix");
        }
        long[][] dp = new long[n + 1][n + 1];
        int[][] opt = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) opt[i][i] = i;

        for (int length = 2; length <= n; length++) {
            for (int i = 1; i <= n - length + 1; i++) {
                int j = i + length - 1;
                int lowK = opt[i][j - 1];
                int highK = Math.min(opt[i + 1][j], j - 1);
                long bestCost = Long.MAX_VALUE / 4;
                int bestK = lowK;
                for (int k = lowK; k <= highK; k++) {
                    long candidate = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
                    if (candidate < bestCost) {
                        bestCost = candidate;
                        bestK = k;
                    }
                }
                dp[i][j] = bestCost;
                opt[i][j] = bestK;
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        long[] sampleDims = {10, 20, 30, 40, 30};  // 4 matrices
        System.out.println("Minimum multiplication cost: " + matrixChainKnuth(sampleDims)); // 30000
    }
}

On p = [10, 20, 30, 40, 30] (four matrices: $10\times20$, $20\times30$, $30\times40$, $40\times30$), the bounded search still finds the global optimum: $dp[1][2]=6000$ with $opt=1$, $dp[2][3]=24000$ with $opt=2$, $dp[3][4]=36000$ with $opt=3$; at length 3, $dp[1][3]$ restricts its search to $k$ between $opt[1][2]=1$ and $opt[2][3]=2$ and finds $18000$ at $k=2$, while $dp[2][4]$ restricts to $k$ between $2$ and $3$ and finds $48000$ at $k=3$; finally $dp[1][4]$ restricts to $k$ between $opt[1][3]=2$ and $opt[2][4]=3$ and finds $30000$ at $k=3$ — the same answer a full $O(n^3)$ scan would find, since checking the excluded $k=1$ candidate directly gives a worse $54000$.

7. Complexity Analysis

Each bound depends on its precondition holding: the monotonic queue needs a genuinely bounded or sliding predecessor window, the divide-and-conquer approach needs a monotone optimal split point, and Knuth's optimization needs the quadrangle inequality and monotonicity. When a recurrence does not satisfy the relevant property, falling back to the naive $O(nk)$, $O(n^2)$, or $O(n^3)$ evaluation is still correct — it is only slower.

8. Applications & Alternatives

These three are not the only DP-acceleration techniques. When the cost function is linear in the transition variable rather than sliding-window-bounded or quadrangle-inequality-bounded, the Convex Hull Trick (or a Li Chao tree) accelerates the same recurrence shape by maintaining a lower envelope of lines — a different structural property from any of the three covered here, and outside this lesson's scope. Choose the technique that matches the property your cost function actually has; none of them applies universally.

9. Exercises and Mastery

Easy

1. Re-read Sliding Window Maximum from the monotonic deque lesson and note that it is the degenerate case of monotonic queue DP optimization where $dp[i] = nums[i]$ has no accumulation term at all — the deque code you already have needs no changes to serve as this section's window-maximum finder.

Medium

1. Apply the divide-and-conquer DP optimization template to partition [4, 8, 15, 16, 23, 42] into $K=3$ contiguous groups minimizing the sum of squared group sums; verify your opt values are non-decreasing across $i$ within each layer, and compare the total candidate-scans performed against a full $O(n^2)$ scan per layer.

Hard

1. Extend the Optimal Binary Search Tree recurrence from Interval DP with Knuth's optimization: verify that its cost function (subtree weight) satisfies the quadrangle inequality, add an opt table to your existing $O(n^3)$ solution, and confirm the accelerated version returns the identical tree cost as the unoptimized version on the same input.

Review rhythm: tomorrow, redraw the split-point sandwich $opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$ from memory and explain why it holds; next week, implement all three techniques in a language you have not used for them yet; several weeks later, before reaching for a full $O(n^2)$ or $O(n^3)$ DP, check whether its cost function has a sliding window, a monotone split point, or the quadrangle inequality. Finally, teach someone who already knows plain DP why "the optimal split point never moves backward" is a claim that must be proven, not assumed.

10. Summary Cheat Sheet

• All three techniques accelerate recurrences of the shape dp[i] = min over j of (dp[j] + cost(j, i)) by exploiting a structural property of cost, not by changing what the DP computes.
• Monotonic queue DP optimization: valid $j$ forms a sliding window — maintain the window's best $dp[j]$ with a monotonic deque, $O(n)$ amortized total.
• Divide-and-conquer DP optimization: the optimal $j$ is monotone non-decreasing in $i$ for a fixed layer — recurse on the midpoint first and bound each half's search range, $O(n \log n)$ per layer.
• Knuth's optimization: $cost$ satisfies the quadrangle inequality in interval DP — bound $opt[i][j]$ between $opt[i][j-1]$ and $opt[i+1][j]$, $O(n^2)$ total instead of $O(n^3)$.
• Always verify the precondition before applying an optimization; none of the three is safe to apply blindly.
• When none of the three properties hold, the Convex Hull Trick handles a linear cost function — a different technique for a different structural property.