DP VII — 2D Grid

Review boundary and corrected contracts

Nonempty rectangular grids and positive dimensions are explicit. Right/down paths form a DAG even with negative cell costs. Dungeon Game is a backward required-health recurrence, not a forward minimum-sum recurrence; the required entering-health state is floored at one, rather than allowing the knight's actual health to drop and then resetting it.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Make grid DP mechanical: every cell is a fixed function of a few fixed neighbours. Master path counting, min-cost paths, and in-grid obstacles as the on-ramp to string DP.

Series: LeetCode — From Basics to Production-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)

Optional resources retained from the original lesson; video availability and contents were not rechecked in this review. The worked explanations below are self-contained.

• Unique Paths — DP — NeetCode.
• Minimum Cost Path — grid DP — Tushar Roy — Coding Made Simple.
• Minimum Path Sum in a grid — recursion to tabulation to O(n) space — take U forward.

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 design review points and makes string DP (L40) feel like the same machine.

Water filling a terraced field

Real: Picture a terraced hillside where water can only flow right or down. To know how much water reaches a given terrace, you sum what flows in from the terrace directly above and the one directly to its left. You can't compute a terrace until both feeders are known — that's the fill order. The top row and left column each have only one feeder — that's the base case.

# grid path counting: only move right or down
# ways(r,c) = ways(r-1,c) + ways(r,c-1)
# top row & left col: exactly one way to reach (all rights / all downs)

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

Question: Why is dp[r][c] a function of only dp[r-1][c] and dp[r][c-1], and why does the fill order matter?

Premise: Moves are restricted to right and down, so the only way to ARRIVE at (r,c) is from directly above (r-1,c) or directly left (r,c-1).

Because: A down-move lands from above; a right-move lands from the left. No other cell can be the immediate predecessor.

Premise: So the answer at (r,c) combines the answers at exactly those two predecessors — summed (counting paths) or min-plus-cost (cheapest path).

Because: Optimal-substructure: the best/counted way to (r,c) extends a best/counted way to one of its two predecessors.

Premise: The first row and first column have only ONE predecessor, so their recurrence degenerates: dp[0][c] depends only on dp[0][c-1], and dp[r][0] only on dp[r-1][0].

Because: There is no cell above the top row nor left of the leftmost column; the missing neighbour is treated as 'unreachable' (0 ways / +∞ cost) or seeded directly.

Premise: Top-to-bottom, left-to-right is one valid fill order: both predecessors are computed before each cell. Column-major order or increasing r+c also works when it respects the same dependencies.

Because: A cell can't read a neighbour that hasn't been filled yet — that's the whole discipline of tabulation.

Conclusion: Grid DP = each cell is a fixed combination of its up and left neighbours; base rows/cols degenerate to one neighbour; fill in an order that respects dependencies.

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

Both examples roll to O(n) space with a single row array, since row r only reads row r-1 and its own left neighbour. Offer the rolled version as your follow-up once the 2D version is on the board.

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

Name: Up and left, fill like reading a page

Picture: A spreadsheet. Every cell's formula points at the cell above and the cell to its left. You fill it the way you read — top row first, then next row, left to right — so both references always already have values. The first row and first column are special: they have only one reference, so their formula is simpler.

• Right/down movement ⇒ predecessors are up and left only.

• Count paths ⇒ sum the two predecessors; min-cost ⇒ cost + min of the two.

• Base row/col have one neighbour — handle them explicitly or seed them.

• If the constraint depends on the DESTINATION (e.g. minimum HP), fill backwards from bottom-right (Dungeon Game).

Trigger: A 2D grid with restricted movement (usually right/down) asking for count, min/max cost, or reachability.

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.

Myth: You can always fill a grid DP forward from the top-left corner.

Truth: Usually yes, but when the answer at a cell depends on what happens AFTER it (like the minimum health needed to survive the rest of the path in Dungeon Game), you must fill BACKWARDS from the destination.

Why: In Dungeon Game, dp[r][c] = min health to enter (r,c) and survive to the end. That depends on dp[r+1][c] and dp[r][c+1] — cells AHEAD of you — so a forward sweep reads unfilled cells. Filling from bottom-right fixes it.

Test: Ask: does this cell's value depend on cells I've already filled, or on cells further along the path? If further along ⇒ reverse the fill direction.

What reviewers actually ask

• LC62 · Unique Paths — Practice selection. 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 — Practice selection. 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 — Practice selection. Cheapest path. Probe: the min-plus recurrence and the infinity/seed handling for the borders.
• LC120 · Triangle — Practice selection. 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 — Practice selection. 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 — Practice selection. 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

A forward sweep of this required-entering-health recurrence fails: its dependencies describe the rest of the path. This does not rule out every forward formulation; for example, a fixed initial-health feasibility check can propagate the maximum surviving health forward. 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.

Worked variant — rolling the table down to one row

Every grid DP in this session has an O(n) space version, but rolling the storage does not choose the direction of the recurrence for you. After Dungeon Game's backwards sweep, return here to Minimum Path Sum: its state describes the cost of arriving at a cell, so we again fill forwards from the entrance. Picture a cursor moving across one row. Behind it are the new row's answers; ahead of it are the previous row's answers. The next update needs one value from each side of that boundary. Minimum Path Sum, rolled:

def min_path_sum_rolled(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
 
    # dp holds ONE row. Before processing row r it holds row r-1;
    # after, it holds row r. This works only because the recurrence
    # reaches exactly one row back and one column left.
    dp = [0] * n
    dp[0] = grid[0][0]
    for c in range(1, n):
        dp[c] = dp[c - 1] + grid[0][c]      # base row: only 'left' exists
 
    for r in range(1, m):
        dp[0] += grid[r][0]                  # base column: only 'up' exists
        for c in range(1, n):
            # At this instant:
            #   dp[c]     is still row r-1  -> the 'UP' neighbour
            #   dp[c-1]   is already row r  -> the 'LEFT' neighbour
            # The read order is what makes one array carry two rows.
            dp[c] = grid[r][c] + min(dp[c], dp[c - 1])
    return dp[-1]
 
assert min_path_sum_rolled([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) == 7

The whole trick is in the comment: the cell you have not yet overwritten is the row above; the cell you just overwrote is the row you are building. Left-to-right iteration makes that true automatically. This also explains why the technique needs adjusting when the recurrence reaches up-right — Minimum Falling Path Sum, LC931 — because in a left-to-right sweep the up-left neighbour has already been clobbered. There you either stash the previous value before each write, or keep two rows and stop being clever.

The rule to carry: distinguish current-row dependencies from previous-row dependencies before overwriting storage. For this right/down recurrence, the current-row left neighbour must already be written, while the previous-row up value must still be old. Reaching only one row back makes two-row storage sufficient; one-row storage additionally requires a safe sweep or saved overwritten values. It is not enough to count how many rows the recurrence reaches.

Worked answers — different neighbour sets

For Triangle, define best[c] as the cheapest suffix starting at column c of the row below. A parent at (r,c) can choose children (r+1,c) or (r+1,c+1); take their minimum and add the parent value. Seed the last row itself. Increasing c is safe in place: best[c+1] has not yet been overwritten. The contract is a nonempty triangle whose row r has r+1 entries.

def triangle_minimum_total(triangle):
    best = triangle[-1][:]
    for r in range(len(triangle) - 2, -1, -1):
        for c in range(r + 1):
            best[c] = triangle[r][c] + min(best[c], best[c + 1])
    return best[0]
 
assert triangle_minimum_total([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]) == 11

For Minimum Falling Path Sum, every first-row cell is a possible start. Each later cell takes the minimum among in-bounds up-left, up and up-right, then adds its value; the answer is the minimum over the last row. Separate old/new rows prevent overwriting the up-left dependency. This works on any nonempty rectangular grid, including negative costs.

def minimum_falling_path_sum(grid):
    previous = grid[0][:]
    n = len(previous)
    for r in range(1, len(grid)):
        row = grid[r]
        current = [0] * n
        for c in range(n):
            current[c] = row[c] + min(previous[k]
                                      for k in range(max(0, c - 1), min(n, c + 2)))
        previous = current
    return min(previous)
 
assert minimum_falling_path_sum([[2, 1, 3], [6, 5, 4], [7, 8, 9]]) == 13

Triangle takes O(number of cells) time and O(number of rows) working space. Falling paths take O(rows × columns) time and O(columns) working space for the old and new numeric rows. Neither function mutates its input.

Common failure modes

1. Seeding the base row and column with 1 in Unique Paths II without checking for obstacles. A wall anywhere in row 0 blocks every cell after it in that row; the base fill must stop at the first obstacle, not continue past it.
2. A blocked start cell. grid[0][0] == 1 means zero paths, and a base fill that unconditionally writes 1 there reports a path that cannot exist.
3. Using 0 as the identity for a minimisation. Min-cost grids need an infinity seed or an explicit base row, otherwise every cell happily inherits a free zero.
4. Rolling the array when the recurrence reaches a neighbour you have already overwritten. Silently reads the current row instead of the row above, producing a plausible wrong number rather than a crash.
5. Filling forward when the value depends on the remaining path. The Dungeon Game trap — the sweep reads unfilled cells, which in a table seeded with zeros looks like data rather than an error.
6. Confusing m and n. Rows is len(grid), columns is len(grid[0]). Swapping them survives on square test grids and fails on the first rectangular one.

Tradeoff

Decision: 2D table vs rolled 1D array for grid DP.

Name: Full 2D dp[r][c]

Gain: Trivial to reason about, easy to reconstruct the actual path by walking back through cells, robust to weird neighbour sets.

Cost: O(mn) space.

Pick: when you need the path itself, or the neighbour pattern is irregular (triangle, falling path).

Name: Rolled 1D array

Gain: O(n) space, the expected optimisation for the standard right/down problems.

Cost: This scalar-only pass discards the history needed for direct path backtracking; reconstruction needs extra work or storage. Preserve the distinction between old-row and new-row entries.

Pick: as the follow-up optimisation after the 2D version, when only the final scalar is required.

Verdict: Show the 2D recurrence first (it proves you understand the dependencies), then roll to 1D. Keep 2D if a reviewer wants the path, not just the value.

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.

You are ready to move on when you can

• Write Unique Paths and Minimum Path Sum from memory, borders handled correctly.

• Handle obstacles by zeroing blocked cells and reason about a blocked first row.

• Roll a grid DP to O(n) space and explain why row r only needs row r-1.

• Recognise when to fill BACKWARDS from the destination (Dungeon Game) and say why.

• Extend the neighbour set for Triangle / Minimum Falling Path Sum.

Self-check (answer follows each question).

Check yourself

Q: When can a grid DP be rolled down to a single row, and how do you know which of dp[c] and dp[c-1] is the 'up' neighbour?

A: Check that every old-row value survives until its last read, saving overwritten values when needed, and that current-row dependencies are already computed. In this right/down recurrence, left-to-right keeps dp[c] at row r-1 (up), while dp[c-1] is row r (left). Falling-path DP also needs the old up-left value, so this naive roll alone is insufficient.

Q: Minimum Falling Path Sum reaches up-left, up, and up-right. Why does the naive single-row roll break, and what fixes it?

A: In a left-to-right sweep the up-right neighbour is still the previous row and is fine, but up-left has already been overwritten with the current row. Fix by stashing the previous value before each write, or by keeping two separate rows.

Q: In Unique Paths, why are the entire first row and first column initialised to 1?

A: There is exactly one way to reach any first-row cell (all rights) and any first-column cell (all downs) — a single monotone path, so 1 way each.

Q: Why can grid DP usually be reduced from O(mn) to O(n) space?

A: Each cell reads only the cell directly above (previous row) and the cell to its left (current row). A single rolling row array plus the left neighbour suffices.

Q: What breaks in Dungeon Game if you fill forward from the top-left?

A: This entering-health state reads the right and lower cells, which an increasing-row/increasing-column sweep has not computed. Fill this recurrence backwards; a different forward state, such as feasibility for a fixed initial health, is a different algorithm.

Q: In Minimum Falling Path Sum, how many predecessors does a cell have and which?

A: Up to three: the cell directly above, and the two diagonals up-left and up-right in the previous row.

Q: Why the max(1, need) floor in Dungeon Game?

A: The knight's health must be at least 1 at every cell to stay alive; if the recurrence suggests a lower or negative requirement, it's floored to 1. Without the floor you would allow health to be topped up by future gains the knight cannot survive long enough to reach.

Stretch: On dungeon [[-2, 5, -10]], the total is -7, but check every prefix: -2, 3, -7. Initial health 8 keeps all resulting health values at least 1. On [[-10, 20]], total +10 does not make initial health 1 safe; the first cell requires 11. A total path sum alone cannot determine survival.

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.

• Grid DP is mechanical: each cell = a fixed function of its up and left neighbours.

• Watch the base row/column (one neighbour) and fill in reading order so dependencies exist.

• Roll to O(n) space; row r needs only row r-1.

• Dungeon Game breaks the forward reflex: when a cell depends on the remaining path, fill backwards from the exit.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.