In interval DP, why can't the dp[i][j] table be filled in plain row-major order?

## The state and where its dependencies live Interval DP solves problems whose subproblem is *a contiguous subrange of a sequence*, not a prefix. The table entry is `dp[i][j]` = the best cost for the piece of the input between positions `i` and `j`. The transition picks a split point `k` strictly inside the range and combines the two halves: ``` dp[i][j] = w(i, j) + min over i < k < j of ( dp[i][k] + dp[k][j] ) ``` where `w(i, j)` is the cost charged for combining (or separating) the whole range once. Every operand on the right — `dp[i][k]` and `dp[k][j]` — covers a **strictly shorter** interval than `[i, j]`, because `i < k < j`. That single fact fixes the entire fill order. ## Why row-major order breaks A linear DP over prefixes has all its dependencies to the left, so the obvious ascending loop works. Interval DP does not. Consider the ascending nest: outer `i` from 0 upward, inner `j` from `i+1` upward. When you compute `dp[i][j]` you need `dp[k][j]` for every `k` between `i` and `j`. Those entries sit in **rows below the current row** — larger first index — and the outer loop has not reached them. They still contain whatever the table was initialized to. This is a nasty failure mode, and it is the reason the question gets asked. Nothing throws. If the table was initialized to a large sentinel, the minimum silently ignores every legitimate split that needed a lower row and you get a too-large answer; if it was initialized to zero, you get a too-small answer that looks plausible on tiny inputs. Small hand-checked cases of size three or four often pass by accident, because with so few positions the missing entries are base cases. The bug shows up only at size five and above. ## The two orders that do work **By interval length (the canonical one).** Iterate `span` from the smallest non-trivial length up to `n-1`; for each `span`, let `i` run over all valid left endpoints and set `j = i + span`. Every entry read has a smaller span and is therefore already final. This order is self-documenting: it makes the dependency structure — shorter intervals first — visible in the loop header, which is why it is the one you should write on a whiteboard. **By decreasing left endpoint.** Iterate `i` from `n-1` down to 0 and `j` from `i+1` up to `n-1`. Now `dp[k][j]` with `k > i` lives in an already-completed row, and `dp[i][k]` with `k < j` lives earlier in the current row. Also correct, marginally friendlier to sequential memory access, and harder for a reviewer to verify at a glance. A third route sidesteps the question entirely: **top-down memoized recursion**. Recursion evaluates dependencies on demand, so you never have to reason about an explicit order — you pay a recursion stack of depth proportional to the interval nesting and a hash-or-array lookup per call instead. The state count and the transition count are unchanged; only the constant factor and the space profile move. ## Base cases The base cases are exactly the intervals with **no valid split point** — the ranges so short that no `k` satisfies `i < k < j`. Depending on how the indices are defined (positions between marks, or elements of a chain), that is the intervals of length one or two. Getting this off by one is the other classic error here: if you leave the shortest intervals uninitialized, the minimum over an empty set of split points leaves a sentinel that then poisons every longer interval that reads it. ## Why this matters beyond the loop nest The fill order is not bookkeeping; it *is* the statement that the recurrence is well-founded. If you cannot name an ordering in which every entry's dependencies precede it, the recurrence has a cycle and is not a valid dynamic program at all. Stating "shorter intervals first" out loud is how you demonstrate to an interviewer that you have checked that property rather than pattern-matched a loop nest from memory. A useful sanity check before writing any code: name the state, name the transition, then name the partial order the transition induces on states. For prefix DP that order is index; for subset DP it is subset size; for interval DP it is interval length. The loop nest is just that order written down.