L39 · DP VII — 2D Grid

Series: LeetCode — From Basics to Interview-Ready · Session 39 / 65 · Phase 2 · Dynamic programming

Prerequisites

L33–L34 (state, recurrence, tabulation). Grid DP is the gentlest place to make DP feel automatic, so if 1D DP is solid but you find state definition fiddly, this session will cement it. It's also the direct warm-up for L40 (string DP), which is grid DP over two strings.

Watch first (skim before the session)

Why this session exists

Grid DP is dynamic programming with training wheels: the state is literally the cell (r, c), and the recurrence reads a couple of fixed neighbours — usually the cell above and the cell to the left. There's almost no state-design creativity required, which makes it the perfect place to make the mechanics — base cases, fill order, rolling-array space reduction — feel automatic.

But it isn't trivial. Three things get people: base rows and columns (the first row and column have only one neighbour, not two), fill order (you must fill a cell only after its dependencies exist), and the occasional problem — Dungeon Game — where the natural fill direction is from the destination backwards, because the constraint propagates the wrong way for a forward fill. Nailing those three turns grid DP into free interview points and makes string DP (L40) feel like the same machine.

Blank-file warm-up

Five minutes, empty file, no notes. Write both cores from memory:

count paths :  dp[r][c] = dp[r-1][c] + dp[r][c-1]     (base: first row/col = 1)
min cost    :  dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])

If the base row/column handling wobbles, that's the thing to drill — it's where the bugs live.

From first principles

Unique Paths — count paths, right/down only:

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]        # first row & col are all 1 (one way each)
    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]
 
assert unique_paths(3, 7) == 28
assert unique_paths(3, 2) == 3

Minimum Path Sum — cheapest path top-left to bottom-right:

def min_path_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0:
                continue
            up = dp[r - 1][c] if r > 0 else float("inf")     # no cell above in row 0
            left = dp[r][c - 1] if c > 0 else float("inf")   # no cell left in col 0
            dp[r][c] = grid[r][c] + min(up, left)
    return dp[m - 1][n - 1]
 
assert min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) == 7   # 1→3→1→1→1

Obstacles: Unique Paths II

An obstacle cell contributes zero ways — you just zero it out and let the recurrence flow around it.

def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1:                       # start blocked
        return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:               # obstacle: unreachable
                dp[r][c] = 0
                continue
            if r == 0 and c == 0:
                continue
            up = dp[r - 1][c] if r > 0 else 0
            left = dp[r][c - 1] if c > 0 else 0
            dp[r][c] = up + left
    return dp[m - 1][n - 1]
 
assert unique_paths_with_obstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]]) == 2

Mental model

Memory hook

"Up plus left, read like a page." Grid DP fills in reading order (top-to-bottom, left-to-right) so the up and left neighbours are always ready. The one exception worth flagging aloud — Dungeon Game — reverses it: "health flows from the exit, so fill from the exit." Two short phrases cover the whole session.

What interviewers actually ask

• LC62 · Unique Paths — Amazon, Bloomberg. Count right/down paths. Probe: the up+left recurrence and base row/col. Follow-up: the O(n) rolled array, or the pure-combinatorics answer C(m+n-2, m-1).
• LC63 · Unique Paths II — Amazon. Obstacles. Probe: zeroing blocked cells and handling a blocked start/first-row correctly (a wall in row 0 blocks everything after it).
• LC64 · Minimum Path Sum — Amazon, Google. Cheapest path. Probe: the min-plus recurrence and the infinity/seed handling for the borders.
• LC120 · Triangle — Amazon. Grid DP on a triangular array, best done bottom-up. Probe: adapting the neighbour set to a non-rectangular grid, and the elegant in-place bottom-up fill.
• LC931 · Minimum Falling Path Sum — Google. Each cell draws from three cells in the row above (up-left, up, up-right). Probe: extending the neighbour set beyond two.
• LC174 · Dungeon Game — Amazon (Hard). The backwards-fill classic. Probe: realising a forward fill fails because health depends on the remaining path, then filling from the destination with a floor of 1 HP.

Escalation ladder: count paths → min/max-cost path → obstacles → non-rectangular grid → backwards fill (destination-dependent). Dungeon Game is the boss because it breaks the forward-fill reflex everything else builds.

A worked backwards-fill: Dungeon Game

Forward DP fails: the knight's required starting health depends on the rest of the path, not the part already walked. So define dp[r][c] = the minimum health needed upon entering (r,c) to survive to the princess, and fill from the bottom-right corner.

def calculate_minimum_hp(dungeon: list[list[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])
    INF = float("inf")
    # dp[r][c] = min HP needed entering (r,c) to reach (m-1,n-1) alive
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    dp[m][n - 1] = dp[m - 1][n] = 1          # one step past the exit: need 1 HP
    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            need = min(dp[r + 1][c], dp[r][c + 1]) - dungeon[r][c]
            dp[r][c] = max(1, need)           # never let health drop below 1
    return dp[0][0]
 
assert calculate_minimum_hp([[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]) == 7

• Complexity: O(mn) time, O(mn) space (rollable to O(n)).
• Why the max(1, ...): health must stay ≥ 1 at every cell, so a cell that would allow negative required-health is floored to 1.

Tradeoff

In practice

Grid DP is the skeleton of sequence alignment (DNA/protein alignment is min-cost grid DP over two sequences — the same machine as L40's string DP), image seam-carving (find the lowest-energy vertical seam = min falling-path sum over a pixel-energy grid), and dynamic-time-warping in speech/gesture recognition. Any time two axes index a cost surface and you're finding an optimal monotone path across it, you're doing grid DP.

Practice queue

Solve in this order; log each as cold / warm / hint / failed.

1. LC62 Unique Paths — count, the gateway.
2. LC63 Unique Paths II — obstacles.
3. LC64 Minimum Path Sum — min-cost path.
4. LC120 Triangle — non-rectangular, bottom-up.
5. LC931 Minimum Falling Path Sum — three predecessors.
6. LC174 Dungeon Game — backwards fill, the boss.