Intervals and matrices

Two table shapes share a chapter because both are two-dimensional and neither is filled row by row. In an interval DP, dp[i][j] is the answer for the contiguous range i..j, and it reads only ranges strictly shorter than itself. In a matrix DP, dp[i][j] is the answer for the cell at row i, column j, and it reads its neighbours above and to the left. The recurrences differ; the trap in both is the order you fill the table in.

Interval DP: length is the loop order

dp[i][j] depends on dp[i][k] and dp[k+1][j] for some split k inside the range. Both of those are shorter than i..j. So the rule is mechanical: iterate by increasing length, and everything a cell needs is already computed. Iterating i and j in the natural nested order reads cells that still hold their initial value, and the answer is quietly wrong rather than crashing.

The triangle of interval states, labelled by length, with the two shorter intervals that a split feeds into the full range100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

INF = float('inf')
dp = [[0 if i == j else INF for j in range(n)] for i in range(n)]

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        for k in range(i, j):                        # every split point
            dp[i][j] = min(dp[i][j],
                           dp[i][k] + dp[k + 1][j] + cost(i, k, j))

Three loops, so about n^2 / 2 states each doing O(n) work: O(n^3). At n = 500 the loose bound is 1.25 x 10^8 and the real count is closer to n^3 / 6 ≈ 2 x 10^7 updates, which is why the constraint table in complexity by counting puts n ≤ 500 opposite O(n^3). Above a thousand, an interval DP is the wrong idea.

Matrix chain multiplication is the plain version: dp[i][j] is the cheapest way to multiply matrices i through j, and the split k is where the final multiplication happens. Merging stones, cutting a rod at given positions and optimal binary search trees are the same three loops with a different cost.

Ask which one is last

The split does not always fall out of the problem. Consider bursting balloons in a row, where popping balloon k earns a[left] * a[k] * a[right] for its current neighbours, and the row closes up after each pop.

Splitting on which balloon is burst first fails. Once it goes, the two sides become adjacent, so the left half's answer depends on what the right half does — the subproblems are not independent and there is no valid recurrence.

Reframe: for the open range (i, j), let k be the balloon burst last. At the moment it pops, everything strictly inside is gone, so its neighbours are exactly i and j — known values, fixed in advance. The two sides never interact.

def max_coins(nums):
    a = [1] + nums + [1]                             # virtual walls of value 1
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                       # length of the open range
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):                # k is burst last
                dp[i][j] = max(dp[i][j],
                               dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
    return dp[0][n - 1]

"Which one is last" is the question to try whenever the obvious split makes the halves depend on each other. It is the same move as picking the right state in what DP actually is: choose the framing under which the future stops depending on the past.

Matrix DP: two directions and a boundary

On a grid where you may step only right or down, dp[i][j] reads dp[i-1][j] and dp[i][j-1]. Row by row, left to right, is a legal order — the same argument as in two sequences.

Minimising a path cost takes a min; counting paths takes a +. Same traversal, different operator, and the boundary means different things in each.

def min_path(grid):
    n, m = len(grid), len(grid[0])
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]
    for j in range(1, m):
        dp[0][j] = dp[0][j - 1] + grid[0][j]         # one way along the top
    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + grid[i][0]         # one way down the side
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[n - 1][m - 1]

The boundary is where the bugs live, and there are three of them worth knowing:

Setting the first row to the cell values instead of their running sum. There is exactly one path along the top edge, so dp[0][j] is the sum of everything to its left, not grid[0][j].

Letting the interior loop touch row 0 or column 0. dp[i-1][j] at i = 0 reads dp[-1][j], which in Python is the last row — no exception, just a wrong answer. Either initialise the boundary and start the loops at 1, or pad the table with a sentinel row and column of infinity.

Continuing the first row past an obstacle. For path counting the boundary is 1s, but a blocked cell makes every cell after it in that row unreachable, so the 1s have to stop there. Filling the first row with 1s unconditionally is the standard wrong answer.

A 1,000 x 1,000 grid is 10^6 cells at constant work — a few milliseconds of real computation. Grid DP is almost never the slow part; it is only ever the wrong part.

In an interview

For an interval problem, say the loop order before the recurrence: "I fill by increasing length, because dp[i][j] reads two strictly shorter ranges." That one sentence covers correctness of the order, which is the thing most candidates leave implicit and then get wrong.

For a grid, write the boundary initialisation before the double loop, out loud: "the first row has one path into it, so it is a running sum." Then check the (0, 0) cell explicitly. Interviewers watch for whether you tested the corner you just wrote.

The mistake that loses points: reaching for the first split. When the two halves are not independent, the recurrence is unsound however carefully you code it. Say "if I remove k first, the halves interact — so let me make k the last one removed instead", and you have shown the judgment the question was set for.

Check yourself

Your interval recurrence is correct but the loop is a plain nested i, j over the upper triangle, and the two-matrix sample passes. Predict what happens on a larger case, and name the one change that fixes it.

It stays silent and gets worse. With i ascending, dp[k+1][j] for every k+1 < j is still at its initial INF, so those splits drop out of the min and only the rightmost split survives — the code returns the cost of one fixed left-to-right parenthesisation: legal, finite, and not minimal. Two matrices pass because there is only one split to choose. Three can already fail: for 100 x 10, 10 x 100 and 100 x 5, the minimum is 10,000 multiplications and the broken order reports 150,000. The change is the outer loop — iterate by increasing length.

You have to maximise the score from removing stones in a row, where removing a stone merges its two neighbours. Which end of the decision do you fix, and how do you settle it before writing any code?

Fix the last removal. The test to run on paper is whether the split leaves the two halves able to change each other's payoff: remove a stone first and the sides become adjacent, so the left half's score depends on what the right half did, and there is no recurrence to write down. Make k the stone removed last inside the open range (i, j) and everything strictly between them is already gone when k goes, so its neighbours are exactly i and j — fixed before the subproblem starts. Run that test on any problem where the row closes up after a removal.

An interval DP has n = 2,000. Is O(n^3) viable, and what does that tell you about the intended solution?

No. The loose bound is 8 x 10^9 and the real count is about n^3 / 6 = 1.3 x 10^9 — 13 seconds at 10^8 operations per second, before Python's constant factor. A bound that size says the intended answer is not an interval DP: look for a greedy rule, a linear scan, or a state that is not a pair of endpoints.