Interval DP (DP over Ranges [i..j]) — Senior Level¶

Interval DP is rarely the bottleneck on a 50-element sequence — but the moment n reaches the hundreds, the O(n³) baseline becomes a latency budget you must defend; the moment the cost function is "almost" quadrangle-convex, a wrong optimization silently returns suboptimal answers; and the moment the state needs a third dimension (removing boxes), the O(n⁴) blowup turns a clean DP into a memory and time incident.

Table of Contents¶

1. Introduction
2. The O(n^3) Scaling Wall
3. When the Optimizations Actually Apply
4. Memory Engineering
5. Top-Down vs Bottom-Up in Production
6. State-Dimension Explosion
7. Code Examples
8. Real Systems Where Interval DP Appears
9. Numerical and Tie-Breaking Concerns
10. Observability and Testing
11. Failure Modes
12. Summary

1. Introduction¶

At the senior level the question is no longer "what is the recurrence" but "what breaks when this runs in production on real inputs?". Interval DP shows up in three production guises that share one engine:

1. Offline optimization — "compute the cheapest parenthesization / merge plan / partition" for a sequence supplied in a batch job. n is moderate (hundreds), the cubic factor is the latency budget.
2. Query-time DP — a service answers "optimal cost for sub-range [i..j]" repeatedly over a fixed sequence. Now you precompute once and serve O(1) reads, and the question is memory.
3. Combinatorial scoring — burst-balloons / removing-boxes style problems where the state has an extra dimension and the O(n⁴) cost is the real risk.

All three reduce to: fill a table over intervals in increasing-length order, where each cell minimizes/maximizes over split points. The senior-level decisions are: how to keep the table cubic (or sub-cubic) and not accidentally quartic; when an O(n²) optimization is sound versus when it silently corrupts the answer; how to bound memory; and how to verify correctness when the optimal structure is too large to inspect by eye.

This document treats those decisions in production terms.

2. The O(n³) Scaling Wall¶

2.1 Where the cubic comes from, concretely¶

O(n²) intervals × O(n) split points = O(n³). For matrix chain on n matrices that is roughly n³/6 inner-loop iterations (only the upper triangle, and the k loop shrinks). Concrete budget on a single modern core (≈ 10⁸–10⁹ simple ops/sec):

The wall is around n ≈ 1000–2000 for interactive latency. Past that you either need an O(n²) optimization (if the cost permits) or a different model.

2.2 The hidden quartic: range-cost recomputation¶

The most common senior-level performance regression is recomputing cost(i, j) inside the k loop. If cost(i, j) is a range sum computed in O(n), the DP silently becomes O(n⁴). Always:

• precompute a prefix-sum array so sum(i..j) is O(1), and
• hoist any k-independent cost term out of the inner loop entirely.

This single discipline is the difference between n = 1000 finishing in a second and timing out.

2.3 Constant-factor levers¶

log factors are absent here; the entire cost is the n³ (or n²) loop, so constants dominate:

• Flat 1D backing array indexed i*n + j instead of array-of-arrays — fewer pointer chases, better cache lines.
• Loop the k-dependent reads contiguously: dp[i][k] walks a row (cache-friendly); dp[k+1][j] walks a column (cache-hostile). For very large n, storing a transposed copy of the column-accessed table can help.
• Branchless min/max or precomputed bounds where the language allows.
• Avoid per-cell allocation in cost closures — inline the arithmetic.

2.4 Parallelism along anti-diagonals¶

All cells of the same interval length are independent — they read only strictly-shorter intervals, already finished. So each length-L "anti-diagonal" of the table can be filled in parallel across threads, with a barrier between lengths. This gives near-linear speedup on the cubic work for large n, with the synchronization cost being one barrier per length (n barriers total). The k loop within a cell is sequential, but there are O(n) independent cells per length to distribute.

3. When the Optimizations Actually Apply¶

Dropping O(n³) to O(n²) is the headline senior win, but applying an optimization whose precondition fails returns a wrong answer that looks plausible — the worst kind of bug.

3.1 Knuth's optimization preconditions¶

Knuth's optimization (sibling 11) requires the DP to have the form

dp[i][j] = min_{i ≤ k < j} ( dp[i][k] + dp[k+1][j] ) + cost(i, j)

with cost depending only on (i, j), and two conditions on cost:

1. Quadrangle inequality (QI): cost(a,c) + cost(b,d) ≤ cost(a,d) + cost(b,c) for a ≤ b ≤ c ≤ d.
2. Monotonicity: cost(b, c) ≤ cost(a, d) for a ≤ b ≤ c ≤ d.

These together force the optimal split opt[i][j] to be monotone: opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]. The k loop then ranges only over [opt[i][j-1], opt[i+1][j]], and the total over all cells telescopes to O(n²).

Which classics qualify: matrix chain, optimal BST (Knuth's original), and stone merging (with a contiguous-merge cost = range sum) all satisfy QI. Verify QI for your cost before trusting the speedup — a range-sum cost satisfies it; an arbitrary cost may not.

3.2 Divide-and-conquer optimization preconditions¶

D&C optimization (sibling 12) targets the layered shape dp[t][j] = min_i (dp[t-1][i] + cost(i, j)) (partition into exactly t groups) and needs the optimal i monotone in j. It gives O(n log n) per layer, O(kn log n) overall. This is not the same shape as the single-table interval DP — do not try to apply it to matrix chain. Recognize the partition-into-m-groups signature.

3.3 The decision flow¶

3.4 Verifying a precondition empirically¶

Before shipping a Knuth-optimized solution, run the O(n³) baseline and the O(n²) optimized version on thousands of random small instances and assert identical answers. If they ever diverge, the QI precondition does not hold for your cost — fall back to the baseline. This empirical check is mandatory; QI proofs are subtle and easy to get wrong.

4. Memory Engineering¶

4.1 The table dominates¶

A dp table of int64 is 8n² bytes: 80 KB at n=100, 8 MB at n=1000, 800 MB at n=10000. The O(n⁴) removing-boxes variant (dp[i][j][carry]) is 8n³ bytes — already 8 MB at n=100 and infeasible at n=1000. Memory, not time, is often the first wall for the 3D variants.

4.2 Only the upper triangle is used¶

Since i ≤ j, half the square table is dead. For tight memory you can pack the upper triangle into a 1D array of size n(n+1)/2, halving the footprint at the cost of a small index computation. Worth it only when n is large enough that the table dominates RAM.

4.3 Reconstruction table trade-off¶

Storing split[i][j] doubles the memory. If you only need the optimal value, drop it. If you need the optimal structure (the actual parenthesization), you have two options: keep the O(n²) split table, or recompute the optimal split on demand during a single recursive pass over the value table (O(n) extra work per reconstruction step, no extra storage). For one-shot reconstruction the recompute approach saves memory; for repeated reconstruction queries cache the split table.

4.4 Streaming length-by-length¶

In a few interval DPs you only ever need the previous one or two diagonals (rare — most need arbitrary shorter sub-ranges). When it does hold, keep only the active diagonals and free the rest, reducing O(n²) space to O(n). Check the dependency carefully: matrix chain needs all shorter sub-ranges, so this does not apply to it; some restricted DPs do permit it.

5. Top-Down vs Bottom-Up in Production¶

Production rule: prototype top-down to get the recurrence right, then port to bottom-up for the hot path. For interval DP the whole triangle is usually needed anyway, so bottom-up's "fills everything" is not wasteful, and its lower constant and stack safety win. Keep top-down only when the reachable subset of (i,j) is genuinely sparse (uncommon for interval DP, common for some 3D variants where many carry values never occur).

6. State-Dimension Explosion¶

6.1 When 2D is not enough¶

A 2D dp[i][j] is correct only when the optimal solution to [i..j] is independent of everything outside it. Removing boxes breaks this: the points from removing a block of color c depend on how many same-colored boxes got attached from outside [i..j]. The fix is a third dimension carry = number of boxes of color box[i] glued to the left:

dp[i][j][c] = max(
    (c+1)² + dp[i+1][j][0],
    max_{m in (i,j], box[m]==box[i]} dp[i+1][m-1][0] + dp[m][j][c+1]
)

This is O(n³) states × O(n) transition = O(n⁴). The senior decision: confirm the extra dimension is necessary (try to prove the 2D version wrong with a counterexample) before paying O(n⁴).

6.2 Symptoms of a missing dimension¶

If your 2D interval DP gives the right answer on tiny inputs but wrong on inputs where the same "color"/value recurs across a split, you are probably missing a state dimension that carries cross-split context. The remedy is to identify the minimal extra information the join needs and add it as a third index — but guard the blowup: prune unreachable carry values (top-down naturally does this).

6.3 Keeping the third dimension bounded¶

The carry dimension is bounded by the count of same-colored boxes, often ≪ n. Indexing the third dimension by the actual achievable carry (not a worst-case n) and using a hash-map memo top-down keeps real-world memory far below the O(n³) worst case. Measure the realized state count in production; it is usually a fraction of the bound.

7. Code Examples¶

7.1 Go — matrix chain, flat array, parallel anti-diagonals sketch¶

package main

import (
    "fmt"
    "sync"
)

func matrixChainFlat(dims []int) int {
    n := len(dims) - 1
    dp := make([]int64, n*n) // flat: dp[i*n+j]
    at := func(i, j int) int { return i*n + j }

    for length := 2; length <= n; length++ {
        // cells of this length are independent -> parallelizable
        var wg sync.WaitGroup
        for i := 0; i+length-1 < n; i++ {
            i := i
            wg.Add(1)
            go func() {
                defer wg.Done()
                j := i + length - 1
                best := int64(1) << 62
                for k := i; k < j; k++ {
                    c := dp[at(i, k)] + dp[at(k+1, j)] +
                        int64(dims[i])*int64(dims[k+1])*int64(dims[j+1])
                    if c < best {
                        best = c
                    }
                }
                dp[at(i, j)] = best
            }()
        }
        wg.Wait() // barrier between lengths
    }
    return int(dp[at(0, n-1)])
}

func main() {
    fmt.Println(matrixChainFlat([]int{10, 30, 5, 60})) // 4500
}

7.2 Java — Knuth-optimized optimal BST (O(n^2)), with baseline cross-check hook¶

public class KnuthOptimalBST {
    // O(n^2) using monotone optimal split (Knuth). cost = range frequency sum.
    static long optimalBST(int[] freq) {
        int n = freq.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + freq[i];
        long[][] dp = new long[n + 1][n + 1];
        int[][] opt = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) { dp[i][i] = freq[i]; opt[i][i] = i; }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i + length - 1 < n; i++) {
                int j = i + length - 1;
                long base = prefix[j + 1] - prefix[i];
                dp[i][j] = Long.MAX_VALUE;
                int lo = opt[i][j - 1], hi = opt[i + 1][j]; // monotone window
                for (int k = lo; k <= hi; k++) {
                    long left = (k > i) ? dp[i][k - 1] : 0;
                    long right = (k < j) ? dp[k + 1][j] : 0;
                    long c = left + right + base;
                    if (c < dp[i][j]) { dp[i][j] = c; opt[i][j] = k; }
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(optimalBST(new int[]{34, 8, 50}));
    }
}

7.3 Python — removing boxes (3D state, top-down with memo)¶

import sys
from functools import lru_cache


def remove_boxes(boxes):
    sys.setrecursionlimit(10000)
    n = len(boxes)

    @lru_cache(maxsize=None)
    def solve(i, j, carry):
        if i > j:
            return 0
        # collapse leading run to reduce state space
        i0, c0 = i, carry
        while i0 + 1 <= j and boxes[i0 + 1] == boxes[i0]:
            i0 += 1
            c0 += 1
        best = (c0 + 1) * (c0 + 1) + solve(i0 + 1, j, 0)
        for m in range(i0 + 1, j + 1):
            if boxes[m] == boxes[i0]:
                best = max(best,
                           solve(i0 + 1, m - 1, 0) + solve(m, j, c0 + 1))
        return best

    return solve(0, n - 1, 0)


if __name__ == "__main__":
    print(remove_boxes([1, 3, 2, 2, 2, 3, 4, 3, 1]))  # 23

7.4 Python — anti-diagonal parallel fill with a thread pool¶

import concurrent.futures as cf


def matrix_chain_parallel(dims, workers=4):
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]

    def fill_cell(i, length):
        j = i + length - 1
        best = float("inf")
        for k in range(i, j):
            c = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
            if c < best:
                best = c
        return i, j, best

    with cf.ThreadPoolExecutor(max_workers=workers) as pool:
        for length in range(2, n + 1):
            # cells of this length are independent (read only shorter intervals)
            futures = [pool.submit(fill_cell, i, length)
                       for i in range(n - length + 1)]
            for f in cf.as_completed(futures):  # barrier: drain before next length
                i, j, best = f.result()
                dp[i][j] = best
    return dp[0][n - 1]


if __name__ == "__main__":
    print(matrix_chain_parallel([10, 30, 5, 60]))  # 4500

Note: CPython's GIL limits real speedup for pure-Python arithmetic; the structure (independent cells per length, barrier between lengths) is what transfers to Go goroutines or Java threads where it yields genuine parallelism. The barrier is mandatory — starting length L+1 before all length-L cells are written reads null/garbage.

7.4b Go — packed upper-triangle storage (halves memory)¶

package main

import "fmt"

// Store only the upper triangle (i <= j) in a 1D slice.
// Index of (i, j): offset[i] + (j - i), where offset accounts for
// shorter rows above. For an n x n upper triangle, total = n(n+1)/2.
type triDP struct {
    n    int
    off  []int
    data []int64
}

func newTriDP(n int) *triDP {
    off := make([]int, n)
    total := 0
    for i := 0; i < n; i++ {
        off[i] = total
        total += n - i // row i holds columns i..n-1
    }
    return &triDP{n: n, off: off, data: make([]int64, total)}
}
func (t *triDP) at(i, j int) int64    { return t.data[t.off[i]+(j-i)] }
func (t *triDP) set(i, j int, v int64) { t.data[t.off[i]+(j-i)] = v }

func matrixChainPacked(dims []int) int64 {
    n := len(dims) - 1
    dp := newTriDP(n)
    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            best := int64(1) << 62
            for k := i; k < j; k++ {
                c := dp.at(i, k) + dp.at(k+1, j) +
                    int64(dims[i])*int64(dims[k+1])*int64(dims[j+1])
                if c < best {
                    best = c
                }
            }
            dp.set(i, j, best)
        }
    }
    return dp.at(0, n-1)
}

func main() {
    fmt.Println(matrixChainPacked([]int{10, 30, 5, 60})) // 4500
}

Packing the triangle uses n(n+1)/2 instead of n² cells — about half the memory, worthwhile when the table is the RAM bottleneck (large n, or the 3D variant where n³/2 vs n³ matters more).

7.5 Capacity-planning checklist before shipping¶

8. Real Systems Where Interval DP Appears¶

Interval DP is not only a competitive-programming trope; it shows up in production systems under different names. Recognizing the shape lets you reuse the same O(n³)-or-better engine.

8.1 Query / expression optimization¶

A database join-order optimizer for a linear (left-deep-or-bushy) chain of joins is matrix-chain in disguise: each adjacent pair of relations can be joined at a cost driven by cardinalities, and the optimal bushy plan decomposes over an outermost join — exactly dp[i][j] = min_k dp[i][k] + dp[k+1][j] + joinCost(i,k,j). Real optimizers cap the chain length (the O(n³) / O(2ⁿ) blow-up is why they use heuristics or dynamic programming only up to a bound) and prune with statistics. The interval-DP core is the textbook special case of System-R-style join enumeration restricted to a chain.

8.2 Tensor contraction ordering¶

Contracting a chain of tensors (a generalization of matrix chain to higher-rank tensors) chooses a contraction order minimizing FLOPs. Deep-learning compilers and einsum optimizers run exactly this interval DP (often called "optimal contraction path") for small chains, falling back to greedy for long ones. The cost term is the product of the contracted dimensions — structurally identical to matrix chain.

8.3 RNA secondary-structure prediction¶

The Nussinov algorithm for RNA folding maximizes base pairs over a sequence and is a textbook interval DP: dp[i][j] = max pairs in [i..j], with a split-or-pair transition. It is O(n³) and one of the oldest production interval DPs in bioinformatics; Zuker's energy-minimization extension adds more cases but keeps the interval structure.

8.4 Text justification and segmentation¶

Optimal line-breaking (Knuth-Plass) and some segmentation problems are layered partition DPs — the D&C-optimization shape dp[t][j] = min_i dp[t-1][i] + cost(i,j) — and benefit from the same monotonicity machinery. They are siblings of interval DP, sharing the convex-cost / monotone-cut engine.

8.5 Why naming matters in code review¶

When a junior submits a hand-rolled O(n³) loop for "best way to combine a pipeline of stages," labeling it interval DP immediately surfaces the right review checklist: increasing-length fill order, prefix-sum cost, QI check for a possible O(n²), and a brute-force oracle test. Pattern recognition is the senior's leverage.

9. Numerical and Tie-Breaking Concerns¶

9.1 Integer overflow in the cost accumulation¶

Matrix-chain costs grow as products of three dimensions summed over O(n) splits; with dimensions up to 10³ and n in the hundreds, intermediate sums exceed 32-bit. Always accumulate in 64-bit; in Go/Java cast operands before the multiply ((long) a * b * c), since the multiply overflows before assignment to a long if the operands are int.

9.2 Floating-point costs (join cardinalities, energies)¶

When the cost is a floating-point estimate (join selectivity, RNA free energy), the min/max comparisons are exact but the ties are fuzzy: two plans with costs differing by 1e-12 may flip under reordering, making the chosen plan non-deterministic across runs/platforms. Mitigation: compare with a tolerance, or quantize costs to a fixed precision before the DP, so the optimal-plan choice is reproducible. Non-determinism in the value is usually harmless; non-determinism in the reconstructed plan breaks plan caches and confuses debugging.

9.3 Deterministic tie-breaking for reconstruction¶

When several splits achieve the same optimum, the reconstructed structure depends on which one the loop records. For reproducible plans, fix a tie-break rule (e.g. smallest k, or use strict < so the first optimum wins) and document it. This matters when the plan is cached, compared across versions, or shown to users — an undocumented tie-break is a silent source of "the plan changed but the cost didn't" bug reports.

9.4 A worked debugging session¶

A production interval DP returns a cost 30% too low on one input. Systematic diagnosis:

1. Reproduce on the minimal input. Shrink the failing sequence until it's n ≤ 6; the bug usually survives shrinking.
2. Run the brute-force oracle (all parenthesizations) on that minimal input. Suppose oracle says 4500, DP says 3000.
3. DP < oracle for a min problem is impossible if the recurrence is sound — it means the DP considered an infeasible combination, i.e. it read a cell that wasn't truly computed (garbage 0). This points at fill order.
4. Print the table after the fill and look for a cell used before it was set. The classic culprit: for i: for j: ascending, reading dp[k+1][j] while still 0.
5. Fix to increasing-length order, re-run: DP now matches oracle.

The lesson: the direction of the error narrows the cause. DP-too-low on a min problem ⇒ infeasible combination ⇒ fill order or missing +∞ init. DP-too-high ⇒ excluded the true optimum ⇒ wrong split bounds or an unjustified Knuth window. This sign-based triage is faster than staring at the recurrence.

9.5 The QI cross-check must use the same arithmetic¶

When validating a Knuth-optimized solver against the baseline, both must use identical arithmetic (same integer width, same float rounding). A baseline in exact integers and a Knuth version in floats can disagree purely from rounding, masking or faking a QI violation. Keep the arithmetic type identical across the two implementations during validation.

10. Observability and Testing¶

An interval-DP result is a single number — one wrong split anywhere looks like any other number. Build in checks from day one.

The single most valuable test is the brute-force oracle: enumerate every parenthesization (Catalan-many, fine for n ≤ 8) and compare to the DP entrywise. It catches the overwhelming majority of bugs — wrong fill order, missing base case, off-by-one split bounds.

8.1 A property-test battery¶

for random sequence of length n in [1, 8]:
    assert dp_bottom_up(seq) == brute_force_all_parenthesizations(seq)
    assert dp_top_down(seq)   == dp_bottom_up(seq)
    if cost satisfies QI:
        assert knuth_opt(seq) == dp_bottom_up(seq)
        assert opt table is monotone (opt[i][j-1] <= opt[i][j] <= opt[i+1][j])
    assert cost(reconstruct(seq)) == dp_bottom_up(seq)   # round-trip

These run on a few hundred random instances per CI build and give high confidence. The baseline-vs-Knuth equality test is especially good at catching a QI assumption that does not actually hold for the problem's cost.

8.2 Production guardrails¶

For a service computing interval-DP answers at scale: log the realized state count and max recursion depth (top-down) so a pathological input stands out; assert the input length is within the O(n³)/O(n⁴) budget and reject or degrade gracefully beyond it; and emit the chosen split table only behind a debug flag (it doubles memory).

11. Failure Modes¶

11.1 Wrong fill order¶

Iterating for i: for j: (both ascending) reads dp[k+1][j] before it is computed, yielding a plausible-but-wrong number. Mitigation: fill by increasing length, or descending i / ascending j; assert the dependency in a comment.

11.2 Hidden quartic from range-cost recomputation¶

A range-sum cost recomputed inside the k loop makes an O(n³) DP O(n⁴). Symptom: n = 500 is fast but n = 1000 is 16× slower than expected. Mitigation: prefix sums; hoist k-independent cost out of the inner loop.

11.3 Unjustified Knuth optimization¶

Applying the monotone-split window when QI does not hold returns a suboptimal answer silently. Mitigation: prove or empirically verify QI; cross-check against the baseline on random instances; assert opt monotonicity.

11.4 Split-point framing on a last-element problem¶

Using a partition recurrence on burst balloons / removing boxes gives wrong answers because the subproblems are not independent. Mitigation: identify whether the operation alters neighbors; if so, use last-element framing (and possibly a third state dimension).

11.5 Missing state dimension¶

A 2D DP on removing-boxes-style problems is correct on small inputs but wrong when a value recurs across a split. Mitigation: add the carry dimension; test with cross-split-recurrence inputs.

11.6 Integer overflow¶

Matrix products dims[i]*dims[k+1]*dims[j+1] or accumulated merge costs exceed 32-bit. Mitigation: 64-bit accumulators; in Java/Go cast operands before multiplying.

11.7 Stack overflow in top-down¶

Deep recursion at large n overflows the native stack. Mitigation: raise the limit, convert to bottom-up, or use an explicit stack. Bottom-up is the production default for the hot path.

11.8 Open/closed interval mismatch¶

Mixing the closed [i..j] split convention with the open (i, j) last-element convention (e.g., wrong k bounds, forgotten sentinel padding) produces boundary errors that survive small tests when the boundaries happen to be benign. Mitigation: pick one convention per problem, document it, and test the actual boundary cells (first and last columns of the table) explicitly.

11.9 Cache-hostile column access at large n¶

The inner loop reads dp[i][k] (a row, contiguous) and dp[k+1][j] (a column, strided). For n in the low thousands the column access thrashes the cache, so wall time can be several times the FLOP estimate. Symptom: n=2000 runs much slower than the n³/6 budget predicts. Mitigation: keep a transposed copy of the table updated in lockstep so both reads are row-contiguous, or block the loops so the working set fits L2. This is a constant-factor failure, not an asymptotic one, but at the scaling wall it decides feasibility.

11.10 Forgetting that some interval DPs are not cubic¶

Assuming every range problem costs O(n³) and budgeting accordingly is itself a failure mode. The stone game (end-choice transition) and palindrome partitioning (linear cut layer over a boolean table) are O(n²); misjudging them as cubic wastes optimization effort, while misjudging a genuinely cubic problem as quadratic under-provisions. Mitigation: count the transition cost explicitly — O(n) splits vs O(1) end-choices — before estimating.

11.11 Append-only and incremental scenarios¶

A subtle production trap: someone wants to append an element to the sequence and update the answer cheaply. Interval DP has no general incremental update — appending one element to the right can change Θ(n) cells (the entire last column) and there is no O(1)/O(log n) patch for arbitrary cost functions. Recomputing the new column is O(n²) (each of n new cells does O(n) splits), giving O(n²) per append, O(n³) total over n appends — the same as a full rebuild. Mitigation: if the workload is append-heavy, question whether interval DP is the right model; some restricted costs admit incremental structures (e.g. SMAWK / Knuth-incremental for QI costs), but the general case has no shortcut. Do not promise O(log n) appends on an interval DP.

11.12 Recursion-vs-iteration answer drift¶

A rare but maddening failure: the top-down and bottom-up versions disagree by a tiny amount. Causes are almost always (a) a base case handled implicitly in one and explicitly in the other (e.g. i > j returns 0 top-down but the bottom-up loop never sets that cell), or (b) different tie-breaking producing different reconstructed plans with equal cost but the test compares plans, not costs. Mitigation: make base cases explicit in both; compare costs not plans unless tie-breaking is pinned.

12. Summary¶

• The interval-DP baseline is O(n³) — O(n²) intervals × O(n) splits — comfortable to n ≈ 1000, beyond which you need an optimization or a different model.
• The most common production regression is the hidden quartic from recomputing a range-sum cost inside the split loop; prefix sums and hoisting k-independent terms are mandatory.
• Knuth's optimization drops O(n³) to O(n²) only when the cost depends on (i,j) alone and satisfies the quadrangle inequality + monotonicity (matrix chain, optimal BST, stone merging qualify); applying it without verifying QI silently returns suboptimal answers. The D&C optimization targets layered partition DPs, a different shape.
• Memory is O(n²) (8n² bytes); the 3D removing-boxes variant is O(n⁴) time and O(n³) space — confirm the extra dimension is necessary before paying for it, and bound the carry dimension to its realized range.
• Bottom-up is the production default (lower constant, stack-safe, cache-friendly diagonal sweep); top-down wins only when the reachable state set is genuinely sparse.
• The cubic work parallelizes cleanly across anti-diagonals (cells of equal length are independent), with one barrier per length.
• Always keep a brute-force oracle and a baseline-vs-optimized cross-check; they catch the fill-order bug, the missing base case, the off-by-one split bounds, and the unjustified-optimization bug that together account for nearly every real defect.

Decision summary¶

• Small n (≤ a few hundred), generic cost → plain O(n³) interval DP; optimize constants only.
• Cost depends on (i,j) and satisfies QI → Knuth optimization, O(n²) (sibling 11).
• Partition into exactly m groups, monotone optimal split → D&C optimization, O(nm log n) (sibling 12).
• Operation alters neighbors (burst/remove) → last-element framing; add a third state dimension if cross-split context matters.
• Subproblems are arbitrary subsets, not contiguous ranges → stop; this is bitmask DP, not interval DP.
• Merges need not be adjacent → stop; this is Huffman/greedy, O(n log n).

References to study further: Knuth's 1971 optimal-BST paper, Yao's 1980 quadrangle-inequality generalization, the divide-and-conquer optimization literature, CLRS Chapter 15, and sibling topics 11-knuth-optimization and 12-divide-and-conquer-optimization.