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)(row, col), where the answer to each cell depends on the cell above and the cell to its left, and an interval [left, right][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.

Grid DP: Unique Paths

A robot starts at the top-left of an m x nm x n grid and can only move right or down. The number of distinct paths to reach cell (r, c)(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

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 minmin 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)

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 11s. The trick: dp[r][c]dp[r][c] holds the side length of the largest square whose bottom-right corner is at (r, c)(r, c). A square of side kk at (r, c)(r, c) requires squares of side at least k - 1k - 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)

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]dp[left][right] answers a question about the subarray or substring from leftleft to rightright, built from smaller sub-ranges nested inside it. Because dp[left][right]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)]

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_pal[i][j] is TrueTrue when s[i:j+1]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")

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_palis_pal table to answer a different question: what’s the minimum number of cuts needed to split ss into palindromic pieces? cuts[end]cuts[end] is 0 if the whole prefix s[0:end+1]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")

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

nn balloons sit in a row, each with a number painted on it. Bursting balloon kk earns nums[left] * nums[k] * nums[right]nums[left] * nums[k] * nums[right] coins, where leftleft and rightright 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]dp[l][r] is the max coins from bursting every balloon strictly between padded boundary balloons ll and rr:

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

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]p[i-1] x p[i], find the parenthesization that minimizes scalar multiplications. dp[i][j]dp[i][j] is the cheapest way to multiply matrices ii through jj, trying every split point kk:

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

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

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]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 <= 2001 <= rows, cols <= 200, 0 <= grid[r][c] <= 2000 <= grid[r][c] <= 200.

Examples. [[1,3,1],[1,5,1],[4,2,1]][[1,3,1],[1,5,1],[4,2,1]] gives 77 (the path 1 -> 3 -> 1 -> 1 -> 11 -> 3 -> 1 -> 1 -> 1) · [[1,2,3],[4,5,6]][[1,2,3],[4,5,6]] gives 1212

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)(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]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]dp[c], the old dp[c]dp[c] is still the cell above and dp[c-1]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 -> 41 -> 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 minmin 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 minmin.

LC 221 — Maximal Square · Medium

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

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

Examples. [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"], ["1","0","0","1","0"]][["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"], ["1","0","0","1","0"]] gives 44 · [["0","1"],["1","0"]][["0","1"],["1","0"]] gives 11

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 minmin of three: a square of side kk at (r, c)(r, c) requires squares of side at least k - 1k - 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""1", not 11. Every one of these constructor-quirk details has cost somebody a submission.
An all-zero matrix returns 0, and bestbest starting at 0 covers it.
The padded row and column mean the border reads zeros rather than needing r > 0 and c > 0r > 0 and c > 0 guards. That is why matrixmatrix is indexed at r - 1, c - 1r - 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 dpdp instead of maxing it, because a cell with dp = kdp = k is the corner of exactly kk squares. “Where is the square?” — record the (r, c)(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 ii earns nums[left] * nums[i] * nums[right]nums[left] * nums[i] * nums[right], where leftleft and rightright 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) <= 3001 <= len(nums) <= 300, 0 <= nums[i] <= 1000 <= nums[i] <= 100.

Examples. [3,1,5,8][3,1,5,8] gives 167167 · [1,5][1,5] gives 1010 · [5][5] gives 55

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 kk first” — fails. Bursting kk 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 kk is the last balloon burst in the open interval (left, right)(left, right). Everything strictly inside has already gone, so at that moment kk’s neighbours are precisely arr[left]arr[left] and arr[right]arr[right] — values that are still standing by definition of the interval being open. The score is arr[left] * arr[k] * arr[right]arr[left] * arr[k] * arr[right], and the two sides (left, k)(left, k) and (k, right)(k, right) are now genuinely independent, because neither can ever see past kk while kk 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 lastlast because the inner loop runs left + 1left + 1 to right - 1right - 1.

Time $O(n^3)$ — $O(n^2)$ intervals times $O(n)$ choices of last. At n = 300n = 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]dp[left][right] depends on strictly shorter intervals, so length-ascending is the only order that has the dependencies ready. Iterating leftleft then rightright naively reads zeros.
Open intervals are the convention that makes it work: dp[left][right]dp[left][right] excludes both endpoints. Mixing in a closed reading is the usual source of off-by-one pain here.
lengthlength starts at 2 because an interval with no balloon inside scores 0, and that is already the initial value.
[1,1][1,1] gives 2, not 3. Both orders burst one balloon for 1 * 1 * 1 = 11 * 1 * 1 = 1 and then the other for 1 * 1 * 1 = 11 * 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)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

#	Problem	Difficulty	The twist
62	Unique Paths	Medium	The grid DP template above (obstacles add a simple “0 if blocked” tweak)
64	Minimum Path Sum	Medium	Same shape, `minmin` instead of a count
221	Maximal Square	Medium	The min-of-three-neighbors recurrence
312	Burst Balloons	Hard	Interval DP by “last balloon burst in the range”
132	Palindrome Partitioning II	Hard	Min cuts, built on a palindrome interval table
5	Longest Palindromic Substring	Medium	The same palindrome interval table, tracking the best range instead of counting cuts

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]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_palis_pal table; Burst Balloons and Matrix Chain Multiplication share the “try every split point kk” 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

DP on Grids and Intervals

What you’ll learn

Grid DP: Unique Paths

Maximal Square

Interval DP: looping by length, not by index

Longest Palindromic Substring

Palindrome Partitioning II

Burst Balloons

Matrix Chain Multiplication: the prototype interval DP

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 64 — Minimum Path Sum · Medium

LC 221 — Maximal Square · Medium

LC 312 — Burst Balloons · Hard

LeetCode problem set

Recap

Was this page helpful?