DP on Grids and Intervals

DP state doesn’t have to be a single prefix index. Two more shapes show up constantly in interviews: a grid cell (row, col), where the answer to each cell depends on the cell above and the cell to its left, and an interval [left, right] over one sequence, where the answer to a range depends on smaller ranges nested inside it.

What you’ll learn

Grid DP: Unique Paths, Minimum Path Sum, and Maximal Square — three problems built on the same “look up and left” recurrence.
Interval DP’s canonical loop shape: iterate by increasing interval length, not by a single index.
Palindrome Partitioning II and Longest Palindromic Substring, both built on a palindrome-interval table.
Burst Balloons and the Matrix Chain Multiplication idea it’s modeled on — picking the best “split point” inside a range.

The cue

Grid DP — the state is a cell:

The input is a 2-D grid and movement is restricted to one direction pair (right/down, or down only). That restriction is what makes it a DP rather than a search: no cell can be reached from a cell that comes after it, so the table has a safe fill order.
The question is “how many paths”, “cheapest path”, “largest square/rectangle”, counting or optimising over routes.

Interval DP — the state is a range dp[left][right]:

The question is about a contiguous range of one sequence, and the answer for a range is built from strictly shorter ranges inside it: palindromes, matrix-chain-style bracketing, bursting balloons, merging stones.
There is a choice of where to split the range, or which element to handle last.

The reframe: grid DP is 2-D DP where the grid is the table, so the only real work is the base row and column. Interval DP is 2-D DP where the two indices are the ends of a range, which forces the loop order — by increasing length, not by index — because a range depends on ranges shorter than itself.

Reach for something else when movement in the grid is unrestricted in all four directions (that is BFS/DFS, because cycles make a fill order impossible), when the grid has weights and arbitrary movement (Dijkstra), or when a range problem has no split choice and a two-pointer sweep suffices.

Grid DP: Unique Paths

A robot starts at the top-left of an m x n grid and can only move right or down. The number of distinct paths to reach cell (r, c) is the sum of the paths to the cell above it and the cell to its left — since those are the only two ways to arrive:

dp[r][c] = dp[r-1][c] + dp[r][c-1], \qquad dp[0][c] = dp[r][0] = 1

unique_paths.py

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]   # top row and left column: exactly 1 path
 
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
 
    return dp[m - 1][n - 1]
 
 
print(unique_paths(3, 7))   # expect 28

Minimum Path Sum is the same shape with a min instead of a sum, and an added grid cost:

dp[r][c] = grid[r][c] + \min\big(dp[r-1][c],\ dp[r][c-1]\big)

min_path_sum.py

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
 
    for c in range(1, n):
        dp[0][c] = dp[0][c - 1] + grid[0][c]     # top row: only one way in, from the left
    for r in range(1, m):
        dp[r][0] = dp[r - 1][0] + grid[r][0]     # left column: only one way in, from above
 
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])
 
    return dp[m - 1][n - 1]
 
 
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print(min_path_sum(grid))   # expect 7  (path 1 -> 3 -> 1 -> 1 -> 1)

Maximal Square

Given a binary grid, find the largest square made entirely of 1s. The trick: dp[r][c] holds the side length of the largest square whose bottom-right corner is at (r, c). A square of side k at (r, c) requires squares of side at least k - 1 immediately above, to the left, and diagonally above-left — so the side length is capped by the smallest of those three, plus one:

dp[r][c] = \begin{cases} 0 & grid[r][c] = 0 \\ 1 + \min\big(dp[r-1][c],\ dp[r][c-1],\ dp[r-1][c-1]\big) & grid[r][c] = 1 \end{cases}

maximal_square.py

def maximal_square(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    best_side = 0
 
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == "1":
                if r == 0 or c == 0:
                    dp[r][c] = 1                 # first row/column: a lone 1 is a 1x1 square
                else:
                    dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
                best_side = max(best_side, dp[r][c])
 
    return best_side * best_side
 
 
grid = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"],
]
print(maximal_square(grid))   # expect 4  (a 2x2 square of 1s)

sketch Minimum Path Sum: filling the grid DP table p5.js

Each cell's cost is its own grid value plus the cheaper of the cell above or to its left. Darker blue = higher accumulated cost; the final bottom-right cell holds the answer.

Interval DP: looping by length, not by index

The second DP shape works over ranges of one sequence: dp[left][right] answers a question about the subarray or substring from left to right, built from smaller sub-ranges nested inside it. Because dp[left][right] depends on ranges shorter than itself, the loop order must go by increasing interval length first, then slide the start position:

interval_dp_shape.py

# The scaffold every interval DP problem shares:
#
# for length in range(2, n + 1):        # shorter intervals must be solved first
#     for start in range(0, n - length + 1):
#         end = start + length - 1
#         for split in range(start, end):     # try every way to break [start, end] in two
#             dp[start][end] = combine(dp[start][split], dp[split + 1][end], ...)
#
# This prints the (start, end) pairs in the exact order a real interval DP
# fills its table -- shortest ranges first, so every dp[start][split] and
# dp[split + 1][end] used above is already computed.
n = 4
order = []
for length in range(1, n + 1):
    for start in range(n - length + 1):
        end = start + length - 1
        order.append((start, end))
 
print(order)   # expect [(0,0),(1,1),(2,2),(3,3),(0,1),(1,2),(2,3),(0,2),(1,3),(0,3)]

Longest Palindromic Substring

is_pal[i][j] is True when s[i:j+1] is a palindrome. A range is a palindrome if its two end characters match and the range strictly inside them is also a palindrome (or is too short to matter):

is\_pal[i][j] = \big(s[i] = s[j]\big) \text{ and } \big(j - i < 2 \text{ or } is\_pal[i+1][j-1]\big)

longest_palindromic_substring.py

def longest_palindrome(s):
    n = len(s)
    if n == 0:
        return ""
    is_pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
 
    for length in range(1, n + 1):           # shorter ranges first
        for start in range(n - length + 1):
            end = start + length - 1
            if s[start] == s[end] and (length <= 2 or is_pal[start + 1][end - 1]):
                is_pal[start][end] = True
                if length > best_len:
                    best_start, best_len = start, length
 
    return s[best_start:best_start + best_len]
 
 
print(longest_palindrome("babad"))   # expect "bab" (or "aba")

Palindrome Partitioning II

Reuse that same is_pal table to answer a different question: what’s the minimum number of cuts needed to split s into palindromic pieces? cuts[end] is 0 if the whole prefix s[0:end+1] is already a palindrome; otherwise it’s the best of trying every possible last palindromic piece:

palindrome_partitioning_ii.py

def min_cut(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
 
    for length in range(1, n + 1):
        for start in range(n - length + 1):
            end = start + length - 1
            if s[start] == s[end] and (length <= 2 or is_pal[start + 1][end - 1]):
                is_pal[start][end] = True
 
    cuts = [0] * n
    for end in range(n):
        if is_pal[0][end]:
            cuts[end] = 0       # the whole prefix is already one palindrome -- zero cuts
            continue
        cuts[end] = min(
            cuts[start - 1] + 1
            for start in range(1, end + 1)
            if is_pal[start][end]
        )
 
    return cuts[n - 1]
 
 
print(min_cut("aab"))   # expect 1  ("aa" | "b")

Burst Balloons

n balloons sit in a row, each with a number painted on it. Bursting balloon k earns nums[left] * nums[k] * nums[right] coins, where left and right are the nearest still-alive neighbors. The trick that makes this an interval DP: think backward — instead of “which balloon do I burst first”, ask “which balloon do I burst last inside this range”. dp[l][r] is the max coins from bursting every balloon strictly between padded boundary balloons l and r:

dp[l][r] = \max_{l < k < r} \Big( dp[l][k] + dp[k][r] + nums[l] \cdot nums[k] \cdot nums[r] \Big)

burst_balloons.py

def max_coins(nums):
    balloons = [1] + nums + [1]     # pad both ends with an invisible "wall" balloon = 1
    n = len(balloons)
    dp = [[0] * n for _ in range(n)]
 
    for length in range(2, n):              # length = distance between the two boundaries
        for l in range(n - length):
            r = l + length
            for k in range(l + 1, r):        # k = last balloon burst inside (l, r)
                dp[l][r] = max(
                    dp[l][r],
                    dp[l][k] + dp[k][r] + balloons[l] * balloons[k] * balloons[r],
                )
 
    return dp[0][n - 1]
 
 
print(max_coins([3, 1, 5, 8]))   # expect 167

Matrix Chain Multiplication: the prototype interval DP

Burst Balloons and Palindrome Partitioning both borrow their loop shape from a classic: given matrices with dimensions p[i-1] x p[i], find the parenthesization that minimizes scalar multiplications. dp[i][j] is the cheapest way to multiply matrices i through j, trying every split point k:

dp[i][j] = \min_{i \le k < j} \Big( dp[i][k] + dp[k+1][j] + p_{i-1} \, p_k \, p_j \Big)

matrix_chain_order.py

def matrix_chain_order(dims):
    n = len(dims) - 1     # number of matrices
    dp = [[0] * (n + 1) for _ in range(n + 1)]
 
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                for k in range(i, j)
            )
 
    return dp[1][n]
 
 
print(matrix_chain_order([40, 20, 30, 10, 30]))   # expect 26000

Dry run

Grid — unique_paths(3, 7). The whole top row and left column are 1 (one way to walk straight there), and every other cell is the sum of the cell above and the cell to the left:

	c0	c1	c2	c3	c4	c5	c6
r0	1	1	1	1	1	1	1
r1	1	2	3	4	5	6	7
r2	1	3	6	10	15	21	28

Answer 28. Two observations worth more than the number:

That is Pascal’s triangle on its side, which is the giveaway that the closed form is $\binom{m+n-2}{m-1}$ — 28 = $\binom{8}{2}$ . Mentioning it earns credit; the DP is still the right answer when obstacles appear, because the combinatorial formula cannot express them.
The base row and column are the only special cases, and they exist because those cells have one predecessor rather than two. Initialising the entire grid to 1 handles both at once — which is why unique_paths is three lines while min_path_sum needs two explicit seeding loops (its base cells accumulate costs rather than being constant).

Grid — min_path_sum([[1,3,1],[1,5,1],[4,2,1]]):

	c0	c1	c2
r0	1	4	5
r1	2	7	6
r2	6	8	7

Answer 7, the path 1 → 3 → 1 → 1 → 1. Note dp[1][2] = 6: it takes the 5 from above rather than the 7 from the left — 1 + min(5, 7). A greedy walk that always steps toward the smaller neighbour goes 1 → 1 → 5 … and loses, because the cheap first step commits you to a worse row.

Interval — longest_palindrome("babad"). Fill order is by increasing length:

length	ranges examined	marked palindromic
1	(0,0) (1,1) (2,2) (3,3) (4,4)	all five — every single character
2	(0,1) (1,2) (2,3) (3,4)	none — `ba`, `ab`, `ba`, `ad` all mismatch
3	(0,2) (1,3) (2,4)	(0,2) `bab`, (1,3) `aba`
4	(0,3) (1,4)	none
5	(0,4)	none

Answer bab (or aba — both are length 3, and the first found wins).

Length 3 reads length 1. is_pal[0][2] needs s[0] == s[2] and is_pal[1][1], which was filled in the length-1 pass. That dependency is the entire reason the outer loop is length and not start index: loop by start and is_pal[1][1] may not exist yet, giving wrong Falses with no error.
The length <= 2 guard replaces a bounds check. For (1,2), the “inside” range would be is_pal[2][1] — an inverted range that means nothing. Short-circuiting on length is cleaner than special-casing an empty interval.
Only the upper triangle is ever used. is_pal[i][j] for i > j is never read, so half the table is waste — acceptable at $O(n^2)$ , and the reason the expand-around-centre solution is preferred in practice ( $O(n^2)$ time but $O(1)$ space).

Pitfalls

Looping interval DP by start index instead of by length. The inner range is not yet computed, so you read a default False/0 and get a wrong answer with no error. This is the defining bug of the pattern — if an interval DP is mysteriously wrong, check the loop order first.
Forgetting that dp[i+1][j-1] can be an inverted range. Guard with a length test (length <= 2), not with an index comparison bolted on afterwards.
Seeding the grid’s base row and column wrongly. unique_paths fills them with 1; min_path_sum must accumulate along them. Copying one page’s initialisation into the other’s problem is a common slip.
Overwriting a value you still need when collapsing a grid to one row. dp[c] must be read as “the row above” before it is written for this row — for right/down movement the natural left-to-right order happens to work, but verify it rather than assuming.
Obstacles set to 0 after the row is seeded. In LC 63 an obstacle in the top row means every cell to its right is unreachable — 0, not 1. Seed the base row with a break at the first obstacle.
Assuming a greedy step works on a grid. min_path_sum’s dry run is the counterexample: the locally cheaper first step loses.
Confusing “split the range” with “pick the last element”. Burst Balloons only works if you choose which balloon is burst last in a range; choosing the first leaves two subproblems whose neighbours depend on each other, and the recurrence stops being a recurrence.
Using interval DP where a two-pointer or centre-expansion is simpler. Longest Palindromic Substring is the classic case: the DP is easier to derive but costs $O(n^2)$ space, while expand-around-centre is the same time in $O(1)$ space.

Interview follow-ups

They ask	What they’re checking	The answer
“Why must interval DP loop by length?”	The core constraint	Because `dp[start][end]` depends on ranges strictly inside it, so every shorter range must already be filled. Looping by start index reads uninitialised cells and silently returns wrong answers
“Unique Paths has a closed form — why bother with the DP?”	Judgement	$\binom{m+n-2}{m-1}$ is exact and $O(\min(m,n))$ , and the DP table is literally Pascal’s triangle. But the moment obstacles appear (LC 63) the formula cannot express them and the DP is unchanged. Say both
“Reduce the grid DP’s space”	The standard optimisation	Each row depends only on the row above, so one row suffices: $O(n)$ instead of $O(mn)$ . Interval DP cannot be collapsed the same way, because a range depends on ranges of every smaller length, not on a fixed offset
“Why is Burst Balloons about the last balloon burst, not the first?”	The subtle part of interval DP	Because after the last one in a range is burst, the two sides never interact again — so the subproblems are independent. Choosing the first leaves each side’s boundary depending on the other, which is not a valid decomposition
“Can you do Longest Palindromic Substring better than $O(n^2)$ space?”	Breadth	Yes — expand around each of the $2n-1$ centres: $O(n^2)$ time, $O(1)$ space. Manacher’s gets $O(n)$ time, and is worth naming even if you do not write it
“The grid allows moving in all four directions”	Boundaries	Then it is no longer a DP: cycles mean there is no safe fill order. It becomes BFS for unweighted, Dijkstra for weighted, or memoised DFS if the grid is strictly increasing along every legal move (LC 329)
“What is the complexity of interval DP with a split loop?”	Complexity reasoning	$O(n^3)$ : $O(n^2)$ ranges times $O(n)$ split points. That is why $n \le 500$ or so in these problems, and why a problem with $n = 10^5$ is telling you it is not interval DP
“Count the paths modulo $10^9+7$ ”	Practical detail	Take the mod inside the loop, not at the end. Python’s big integers make the unmodded version correct but slow, and in any other language it overflows

Time and space complexity

Problem	Time	Space
Unique Paths / Min Path Sum	$O(mn)$	$O(mn)$ (or $O(n)$ rolling)
Maximal Square	$O(mn)$	$O(mn)$ (or $O(n)$ rolling)
Palindrome tables (substring / partitioning)	$O(n^2)$	$O(n^2)$
Burst Balloons / Matrix Chain	$O(n^3)$	$O(n^2)$

When to use it

Grid DP: the question is about moving through a 2D grid (paths, costs, obstacles) or growing a shape (square, rectangle) from a 2D binary/weighted grid.
Interval DP: the question is about a range of one sequence, and the answer to a range is built from the answers to smaller ranges nested inside it — string partitioning, matrix chains, “remove all of X and score points based on neighbors”.
If you catch yourself trying to loop by a single index and it doesn’t work because dp[i] depends on ranges both smaller and not yet computed, that’s the signal to switch to the length-first interval DP loop order.

Practice — real LeetCode problems

The first two are grid DP, where the table is the grid. The third is interval DP, where you loop by length and choose which element is handled last — the single most counter-intuitive move in the whole DP section.

LC 64 — Minimum Path Sum · Medium

Problem. Given a grid of non-negative numbers, find a path from top-left to bottom-right that minimises the sum of the visited cells. You may only move right or down.

Constraints. 1 <= rows, cols <= 200, 0 <= grid[r][c] <= 200.

Examples. [[1,3,1],[1,5,1],[4,2,1]] gives 7 (the path 1 -> 3 -> 1 -> 1 -> 1) · [[1,2,3],[4,5,6]] gives 12

Editorial · approach, complexity, follow-ups

Grid DP in its purest form. Right-and-down movement means the dependency graph is already topologically sorted by (row, col), so a plain double loop is a valid evaluation order — no recursion, no visited set.

Time $O(rc)$ . Space $O(c)$ with the rolling row, or $O(1)$ if you are allowed to mutate the input grid in place.

The borders have one predecessor, not two. Reaching for dp[r-1][c] on row 0 either crashes or silently reads the wrong row.
The rolling array works because of the read order. At the moment you compute dp[c], the old dp[c] is still the cell above and dp[c-1] has already been updated to this row’s cell on the left. Both are exactly what the recurrence wants. Being able to explain that is the point of the exercise.
A 1x1 grid must return its only cell, which the initialisation gives you before either loop runs.
Greedy fails. Always stepping to the smaller neighbour goes 1 -> 1 -> 4 on the example and misses the optimum. A cheap first step can wall you into an expensive row.

Follow-ups you should expect: “Count the paths instead (LC 62)?” — replace min with +. “Obstacles (LC 63)?” — set blocked cells to 0 ways, and mind that an obstacle in the top row zeros the whole rest of that row. “All four directions allowed?” — the grid stops being a DAG, so it is Dijkstra, not DP. “Negative weights with four directions?” — Bellman-Ford, and negative cycles make it meaningless. “Print the path?” — keep the full 2D table and walk back from the corner. “Diagonal moves too?” — one more term in the min.

LC 221 — Maximal Square · Medium

Problem. Given a binary matrix of "0" and "1" characters, find the largest square containing only "1"s and return its area.

Constraints. 1 <= rows, cols <= 300, entries are the characters "0" or "1".

Examples. [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"], ["1","0","0","1","0"]] gives 4 · [["0","1"],["1","0"]] gives 1

Editorial · approach, complexity, follow-ups

The state that makes this easy is “largest square ending at this cell as its bottom-right corner”. Anchoring a shape to one distinguished cell is a move worth internalising — it turns a 2D search over rectangles into a scan over cells.

Why the min of three: a square of side k at (r, c) requires squares of side at least k - 1 at the cell above, the cell to the left, and the diagonal cell. Two of them are not enough — if you drop the diagonal term, an L-shaped block of ones reports a square that is not there.

Time $O(rc)$ . Space $O(rc)$ , reducible to $O(c)$ with one row plus a saved diagonal value.

Return the area, not the side. Side 2 means answer 4. Reading the question is half the marks.
The entries are strings, so compare against "1", not 1. Every one of these constructor-quirk details has cost somebody a submission.
An all-zero matrix returns 0, and best starting at 0 covers it.
The padded row and column mean the border reads zeros rather than needing r > 0 and c > 0 guards. That is why matrix is indexed at r - 1, c - 1.

Follow-ups you should expect: “Largest rectangle of ones (LC 85)?” — a different problem entirely: build a histogram per row and run the monotonic-stack Largest Rectangle in Histogram. The square version is easy precisely because a square has one free parameter. “Count all square submatrices of ones (LC 1277)?” — sum dp instead of maxing it, because a cell with dp = k is the corner of exactly k squares. “Where is the square?” — record the (r, c) that produced the best side; the corner and the side determine it. “Ones and zeros both allowed?” — run it twice.

LC 312 — Burst Balloons · Hard

Problem. Bursting balloon i earns nums[left] * nums[i] * nums[right], where left and right are its currently adjacent balloons; out-of-range neighbours count as 1. After bursting, the gap closes. Maximise the total coins.

Constraints. 1 <= len(nums) <= 300, 0 <= nums[i] <= 100.

Examples. [3,1,5,8] gives 167 · [1,5] gives 10 · [5] gives 5

Editorial · approach, complexity, follow-ups

The hardest DP on this page, and the difficulty is entirely in the framing.

The natural attempt — “suppose I burst balloon k first” — fails. Bursting k splices the array, so the left and right pieces become adjacent to each other and their subproblems are no longer independent. DP needs subproblems that do not talk to each other.

Flip it. Suppose k is the last balloon burst in the open interval (left, right). Everything strictly inside has already gone, so at that moment k’s neighbours are precisely arr[left] and arr[right] — values that are still standing by definition of the interval being open. The score is arr[left] * arr[k] * arr[right], and the two sides (left, k) and (k, right) are now genuinely independent, because neither can ever see past k while k is still there.

Padding with 1s turns the out-of-range neighbour rule into ordinary array access, and the padded balloons are never candidates for last because the inner loop runs left + 1 to right - 1.

Time $O(n^3)$ — $O(n^2)$ intervals times $O(n)$ choices of last. At n = 300 that is about $2.7 \times 10^7$ , which is why the constraint is 300. Space $O(n^2)$ .

Loop by length, not by index. dp[left][right] depends on strictly shorter intervals, so length-ascending is the only order that has the dependencies ready. Iterating left then right naively reads zeros.
Open intervals are the convention that makes it work: dp[left][right] excludes both endpoints. Mixing in a closed reading is the usual source of off-by-one pain here.
length starts at 2 because an interval with no balloon inside scores 0, and that is already the initial value.
[1,1] gives 2, not 3. Both orders burst one balloon for 1 * 1 * 1 = 1 and then the other for 1 * 1 * 1 = 1. Trace it — guessing 3 here is a very easy mistake to make.
Zeros in the input are free to burst and score nothing; the DP needs no special handling, but a greedy would be badly confused by them.

Follow-ups you should expect: “Why not greedy on the largest product?” — a counterexample is easy to build, because bursting a big balloon early destroys the multiplier its neighbours needed. “Minimum Cost to Merge Stones, or Matrix Chain Multiplication?” — the same shape: loop by length, split at the last operation. “Remove Boxes (LC 546)?” — interval DP with a third dimension. “Can you memoize top-down instead?” — yes, and many find dfs(left, right) easier to reason about; identical complexity. “Can it be done in $O(n^2)$ ?” — not by any known general method; for this problem $O(n^3)$ is the expected answer.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

8 problems

0 easy6 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

5Longest Palindromic SubstringmediumThe same palindrome interval table, tracking the best range instead of counting cutsNeetCode 150Blind 75LeetCode Top Interview 150
62Unique PathsmediumThe grid DP template above (obstacles add a simple "0 if blocked" tweak)NeetCode 150Blind 75
63Unique Paths IImediumLeetCode Top Interview 150
64Minimum Path SummediumSame shape, `min` instead of a countLeetCode Top Interview 150
120TrianglemediumLeetCode Top Interview 150
221Maximal SquaremediumThe min-of-three-neighbors recurrenceLeetCode Top Interview 150
312Burst BalloonshardInterval DP by "last balloon burst in the range"NeetCode 150
329Longest Increasing Path in a MatrixhardNeetCode 150

The variant map

Problem	Shape	`dp` state	The one thing that changes
LC 62 Unique Paths	grid	paths to `(r, c)`	base row and column are all 1
LC 63 Unique Paths II	grid	paths to `(r, c)`	an obstacle forces `dp = 0`; seed the base row with a `break` at the first obstacle
LC 64 Min Path Sum	grid	cheapest route to `(r, c)`	`min` instead of `+`, and the base row/column accumulate
LC 120 Triangle	grid	best route to row `r`, index `i`	ragged rows; bottom-up avoids all the boundary cases
LC 221 Maximal Square	grid	side of the largest square ending at `(r, c)`	`1 + min` of three neighbours — up, left, and up-left
LC 931 Min Falling Path Sum	grid	—	three predecessors instead of two, and the answer is `min` over the last row
LC 5 Longest Palindromic Substring	interval	is `s[i..j]` a palindrome	expand-around-centre is the same time in $O(1)$ space
LC 516 Longest Palindromic Subsequence	interval	best subsequence in `s[i..j]`	non-contiguous, so it is LCS of `s` and `reversed(s)`
LC 312 Burst Balloons	interval	best score from `(i, j)` exclusive	pick the balloon burst last; pad the ends with 1
LC 1000 Merge Stones	interval	+ a third dimension for pile count	splits must respect `(k-1)` divisibility
LC 132 Palindrome Partitioning II	interval + 1-D	—	precompute the palindrome table, then run a 1-D DP over cut positions
LC 329 Longest Increasing Path in a Matrix	grid, all directions	—	not fillable in row order — memoised DFS, since strict increase forbids cycles

Self-check

pch.quizTag Grid and interval DP — self-check

Why must an interval DP's outer loop iterate over range LENGTH rather than start index?

pch.quizShowAnswer

B — Because dp[start][end] depends on strictly shorter ranges inside it, so those must already be filled — looping by start index reads uninitialised cells and returns a wrong answer with no error — In the 'babad' trace, is_pal[0][2] needs is_pal[1][1], which the length-1 pass supplied. This is the defining bug of the pattern: if an interval DP is mysteriously wrong, check the loop order before the recurrence.
Unique Paths has the closed form C(m+n-2, m-1). Why learn the DP?

pch.quizShowAnswer

B — Because obstacles (LC 63) cannot be expressed in the formula, while the DP is unchanged — and the DP table is literally Pascal's triangle, which is worth pointing out — 28 = C(8,2) on the 3×7 grid. Naming both — the O(min(m,n)) formula and the DP that survives added constraints — is a better answer than either alone.
In Burst Balloons, why is the state 'which balloon is burst LAST in this range' rather than first?

pch.quizShowAnswer

B — Because once the last one in a range is burst, the two sides never interact again, so the subproblems are independent. Choosing the first leaves each side's boundary depending on the other, which is not a valid decomposition — This is the single insight that makes LC 312 tractable, and it is why the problem is considered hard despite a short solution. Independence of subproblems is a requirement, not a convenience.
Which of these can be collapsed to O(n) space, and which cannot?

pch.quizShowAnswer

B — Grid DP can — each row depends only on the row above. Interval DP cannot in the same way, because a range depends on ranges of every smaller length rather than a fixed offset — Recognising WHY the rolling trick applies — a fixed reach-back — rather than treating it as a universal DP optimisation is the transferable part.
The grid now allows movement in all four directions. Is it still a DP?

pch.quizShowAnswer

B — No — cycles mean there is no safe fill order. It becomes BFS (unweighted), Dijkstra (weighted), or memoised DFS if some strict monotonicity forbids cycles, as in LC 329 — The restriction to right/down is exactly what guarantees a topological order over cells. LC 329 works because 'strictly increasing' supplies that order instead.
An interval DP with a split loop is O(n³). What does that tell you about the constraints?

pch.quizShowAnswer

B — That n is small — a few hundred at most. A range problem with n = 10^5 is signalling that interval DP is the wrong tool — O(n²) ranges × O(n) splits. Reading the constraints backwards to infer the intended technique is a genuinely useful interview and contest skill.

Recall card

Grid DP cue — 2-D grid, movement restricted to right/down; count or optimise routes. The grid is the table; the only work is the base row and column.
dp[r][c] = dp[r-1][c] + dp[r][c-1] for counting; grid[r][c] + min(up, left) for cheapest; 1 + min(up, left, up-left) for maximal square.
Grid space — one rolling row, $O(n)$ .
Interval DP cue — a question about a contiguous range answered from strictly shorter ranges inside it; usually a choice of split point.
Loop by increasing LENGTH, then start; end = start + length - 1. Looping by index is the pattern’s defining bug.
Guard short ranges by length (length <= 2), not by index arithmetic on an inverted range.
Burst Balloons — choose the balloon burst last, so the two sides stay independent.
Cost — grid $O(mn)$ ; interval $O(n^2)$ states, $O(n^3)$ with a split loop, so expect $n \le$ a few hundred.
Four-directional movement is not DP — no fill order exists. BFS, Dijkstra, or memoised DFS under strict monotonicity.

Recap

Grid DP fills a 2D table where each cell depends on the cell above and the cell to its left (or a similarly small local neighborhood).
Interval DP fills dp[left][right] by looping over increasing interval length first, so every smaller sub-range is already solved before it’s needed.
Palindrome problems (substring, partitioning) share one is_pal table; Burst Balloons and Matrix Chain Multiplication share the “try every split point k” shape.
Recognizing which shape applies — prefix, grid, or interval — is most of the battle in DP interview questions.

Next: Bitmask and Tree DP — when the state is a subset of items or an entire tree, instead of an index, a cell, or a range.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading