DP on Grids

Dynamic programming (DP) on grids is one of the most common DP patterns in coding interviews and real algorithms. You’re given a 2D grid and asked to find the number of ways to reach a target cell, the minimum or maximum cost of a path through the grid, or some other optimal value — usually while moving in restricted directions like right and down. It matters because a handful of ideas solve a huge family of problems: unique paths, minimum path sum, obstacle grids, triangle problems, and more. Once you recognize the pattern — build a table shaped like the grid, fill each cell from the cells that feed into it, read the answer off the last cell — grid DP problems stop feeling like separate puzzles and start feeling like the same problem in different clothes.

Overview: How Grid DP Works

Picture a robot standing at the top-left corner of a grid. It can only move right or down, one cell at a time, and it wants to reach the bottom-right corner. How many distinct paths can it take? Trying to enumerate every path directly is wasteful: many partial paths share the same sub-route, and you’d recompute the same work over and over. That repetition — overlapping subproblems — is the first signal that DP applies.

The second signal is optimal substructure: the number of ways to reach cell (i, j) depends only on the number of ways to reach the cells that can move into it. Since the robot can only arrive at (i, j) from directly above (i - 1, j) or directly to the left (i, j - 1), the count at (i, j) is simply the sum of those two: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]. The base cases are the first row and first column: there’s exactly one way to reach any cell along the top edge (keep moving right) or the left edge (keep moving down), so they’re all initialized to 1.

This is the essence of grid DP: define dp[i][j] as the answer to the subproblem "best/only way to reach cell (i, j)", write a recurrence that expresses it in terms of the cells that can reach it, fill in the base row/column first, and then sweep through the rest of the table in an order that guarantees every dependency is already computed. Because the dependency direction is always top-to-bottom and left-to-right, a simple pair of nested loops (bottom-up tabulation) fills the table correctly without recursion. You can also solve the same problems top-down with recursion plus a memo dictionary or 2D cache — useful when only some cells are actually needed — but tabulation is usually preferred for grids because the fill order is so natural and it avoids Python’s recursion-depth limit on large grids.

The exact recurrence changes with the problem: counting paths sums the predecessors; minimizing or maximizing a path cost takes the min or max of the predecessors plus the current cell’s cost; obstacle problems zero out blocked cells so they can never contribute to a path. But the skeleton — a table shaped like the grid, a recurrence over top/left (or top/left/diagonal) neighbors, base cases along the first row and column — stays the same.

Time and Space Complexity

Let rows and cols be the grid’s dimensions, and n = rows × cols be the total number of cells.

Approach	Time	Space	Why
Bottom-up, full 2D table	O(rows × cols)	O(rows × cols)	Every cell is computed exactly once in constant work; the table stores every cell.
Bottom-up, rolling 1D array	O(rows × cols)	O(cols)	Each row’s values depend only on the row directly above and the current row being built left to right, so you never need to keep older rows around.
Top-down recursion + memo	O(rows × cols)	O(rows × cols) memo + O(rows + cols) call stack	Each distinct (row, col) pair is computed once and cached; the recursion depth is bounded by the longest path from the start cell.

The time complexity is always proportional to the number of cells because the recurrence does O(1) work per cell (a couple of array lookups, an addition or a min/max). It’s never better than O(rows × cols) because, in the worst case, every cell genuinely needs to be visited — there’s no way to skip cells and still guarantee correctness for an arbitrary grid.

Examples

Example 1: Unique Paths

How many distinct paths are there from the top-left to the bottom-right of a 3 × 7 grid, moving only right or down?

def unique_paths(rows: int, cols: int) -> int:
    dp = [[1] * cols for _ in range(rows)]
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[rows - 1][cols - 1]


if __name__ == "__main__":
    result = unique_paths(3, 7)
    print(result)

Output:

28

The table starts as all 1s (the base case for row 0 and column 0 is already satisfied since every cell was initialized to 1). Row 1 becomes [1, 2, 3, 4, 5, 6, 7] — each entry is the cell above (always 1) plus the running total to its left. Row 2 becomes [1, 3, 6, 10, 15, 21, 28], since each entry adds the value above it (from row 1) to the running total to its left. The final cell, dp[2][6], holds the answer: 28 distinct paths.

Example 2: Minimum Path Sum

Given a grid of non-negative costs, find the minimum total cost of a path from the top-left to the bottom-right, moving only right or down.

def min_path_sum(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]

    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

    return dp[rows - 1][cols - 1]


if __name__ == "__main__":
    grid = [
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1],
    ]
    print(min_path_sum(grid))

Output:

7

The first row can only be reached by moving right, so it accumulates: [1, 4, 5]. The first column can only be reached by moving down: dp[1][0] = 2, dp[2][0] = 6. From there, dp[1][1] = 5 + min(4, 2) = 7, dp[1][2] = 1 + min(5, 7) = 6, dp[2][1] = 2 + min(7, 6) = 8, and finally dp[2][2] = 1 + min(6, 8) = 7. The cheapest path is 1 → 3 → 1 → 1 → 1, costing 7.

Example 3: Unique Paths with Obstacles

Real grids often have blocked cells. A 1 marks an obstacle the robot cannot enter; a 0 is open.

def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            elif i == 0:
                dp[i][j] = dp[i][j - 1]
            elif j == 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[rows - 1][cols - 1]


if __name__ == "__main__":
    grid = [
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0],
    ]
    print(unique_paths_with_obstacles(grid))

Output:

2

Row 0 becomes [1, 1, 1] (open path along the top). Column 0 becomes [1, 1, 1] (open path down the left side). The obstacle at (1, 1) forces dp[1][1] = 0 regardless of what feeds into it. That zero then propagates: dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1, dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1, and dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2. There are exactly 2 ways around the obstacle.

How It Works Step by Step

Trace unique_paths on a 3 × 3 grid by hand, following the exact order the nested loops visit cells (i from 1, j from 1). The table starts as all 1s:

1 1 1
1 1 1
1 1 1

1. (i=1, j=1): dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
2. (i=1, j=2): dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
3. (i=2, j=1): dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
4. (i=2, j=2): dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

The final table is:

1 1 1
1 2 3
1 3 6

The bottom-right cell, 6, is the answer — matching the combinatorial identity for this problem (choosing which 2 of the 4 total moves are "down": C(4, 2) = 6). Watching the table fill in this order makes the dependency structure concrete: by the time the loop reaches (2, 2), both dp[1][2] and dp[2][1] already hold their final values, because the loop always processes a row above and a column to the left before it needs them.

Common Mistakes

Mistake 1: Relying on negative indexing instead of explicit base cases

Python allows negative list indices, and it’s tempting to skip initializing the first row and column separately, hoping the recurrence "just works" for i = 0 or j = 0. It doesn’t — it silently produces wrong answers instead of crashing:

def min_path_sum_buggy(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]

When i == 0, dp[i - 1][j] becomes dp[-1][j], which Python happily resolves to the last row of the table instead of raising an error. Likewise dp[i][j - 1] at j == 0 wraps to the last column of the current row. Since the table starts full of zeros, early cells look deceptively correct, but the corruption compounds as the loop fills in later rows, and the final answer is wrong with no exception raised to warn you. Always initialize the first row and column explicitly (as in Example 2) so the recurrence only ever runs where both neighbors are guaranteed to be valid, already-computed cells.

Mistake 2: A mutable default argument as a memo cache

Top-down grid DP is often written with a memo dictionary as a default parameter. That default is created once, when the function is defined — not once per call — so it silently persists across separate calls:

def min_path_sum_recursive(grid: list[list[int]], row: int, col: int, memo: dict = {}) -> int:
    if row == 0 and col == 0:
        return grid[0][0]
    if row < 0 or col < 0:
        return float("inf")
    if (row, col) in memo:
        return memo[(row, col)]
    memo[(row, col)] = grid[row][col] + min(
        min_path_sum_recursive(grid, row - 1, col, memo),
        min_path_sum_recursive(grid, row, col - 1, memo),
    )
    return memo[(row, col)]

Call this once for one grid, then again for a different grid of the same shape, and the second call reuses cached values keyed by (row, col) from the first grid’s costs — the coordinates match, but the underlying data doesn’t, so the answer is silently wrong. The fix is the standard Python idiom: default the parameter to None and create a fresh dictionary inside the function body.

def min_path_sum_recursive(grid: list[list[int]], row: int, col: int, memo: dict | None = None) -> int:
    if memo is None:
        memo = {}
    if row == 0 and col == 0:
        return grid[0][0]
    if row < 0 or col < 0:
        return float("inf")
    if (row, col) in memo:
        return memo[(row, col)]
    memo[(row, col)] = grid[row][col] + min(
        min_path_sum_recursive(grid, row - 1, col, memo),
        min_path_sum_recursive(grid, row, col - 1, memo),
    )
    return memo[(row, col)]

Now every top-level call starts with its own empty memo, and passing memo along in recursive calls still shares the cache correctly within a single call tree.

Best Practices

• Always initialize the first row and first column explicitly before running the general recurrence — never rely on negative-index wraparound to act as a base case.
• Default to bottom-up tabulation for grid DP; the fill order (top-to-bottom, left-to-right) matches the dependency structure exactly, and it sidesteps Python’s recursion-depth limit on large grids.
• If memory is tight and each row only depends on the row above it, collapse the 2D table to a single rolling 1D array of length cols, updating it in place as you sweep down the rows — this drops space from O(rows × cols) to O(cols).
• For obstacle or blocked-cell variants, set the blocked cell’s DP value to 0 for path-counting problems (so it contributes zero ways) or to infinity for min/max-cost problems (so it’s never chosen) — don’t skip the cell, since neighbors still need a defined value to read.
• Never default a memo argument to a mutable object ({} or []); default to None and initialize inside the function.
• Validate that the grid is non-empty and rectangular (every row the same length) before indexing into it — a ragged grid will raise a confusing IndexError deep inside the recurrence otherwise.

Practice Exercises

Exercise 1: Maximum Path Sum

Given a grid of non-negative integers, find the maximum possible sum along a path from the top-left to the bottom-right, moving only right or down. Hint: it’s min_path_sum with every min swapped for max. On the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]], the expected output is 12 (via the path 1 → 3 → 5 → 2 → 1).

Exercise 2: Longest Increasing Path in a Matrix

Given a grid of integers, find the length of the longest path where each step moves to a strictly larger neighboring value (up, down, left, or right — not just right/down). Hint: this needs top-down DFS with memoization, since the "allowed direction" isn’t fixed like in the earlier examples — from any cell you can move to any of its four neighbors as long as the value strictly increases, so a simple left-to-right, top-to-bottom sweep won’t respect all dependencies.

Exercise 3: Minimum Cost with Diagonal Moves

Modify min_path_sum so the robot may move right, down, or diagonally down-right. Hint: each interior cell now has three possible predecessors instead of two — extend the recurrence to dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]), and think carefully about how that changes the base-case handling for the first row and column.

Summary

• Grid DP defines dp[i][j] as the answer to a subproblem at cell (i, j), built from a recurrence over the cells that can reach it (typically above and/or left).
• Base cases live along the first row and first column, since those cells have only one possible direction of approach.
• Time complexity is O(rows × cols) because each cell does O(1) work exactly once; space is O(rows × cols) for a full table or O(cols) with a rolling-array optimization.
• Obstacles are handled by zeroing (path counting) or infinity-ing (min/max cost) the blocked cell rather than skipping it.
• Never rely on negative-index wraparound as an implicit base case, and never default a memo parameter to a mutable object — both are silent-wrong-answer bugs, not crashes.
• Bottom-up tabulation is usually preferred for grids since the natural row-by-row, column-by-column fill order matches the dependency structure and avoids recursion-depth issues.