Grid / 2D Path DP

A robot sits at the top-left corner of an $m \times n$ grid and wants to reach the bottom-right corner. It can only move right or down at each step. How many distinct paths can it take? This is the unique paths problem, and it is the purest introduction to 2D dynamic programming on a grid.

Counting paths

For LeetCode 62, we define dp[i][j] as the number of distinct paths from the top-left corner to cell (i, j). The robot can only arrive at (i, j) from directly above, cell (i-1, j), or from the left, cell (i, j-1). There is no other way, since movement is restricted to right and down. So the recurrence is simply:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

The base cases are the first row and first column. Every cell in the first row can only be reached by moving right from the start, so dp[0][j] = 1 for all j. Every cell in the first column can only be reached by moving down from the start, so dp[i][0] = 1 for all i. Fill in the rest of the table row by row, and dp[m-1][n-1] is the answer.

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

For a $3 \times 3$ grid, the table looks like this:

1  1  1
1  2  3
1  3  6

There are 6 distinct paths. Each path consists of exactly 2 down-moves and 2 right-moves in some order, and 6 = C(4, 2). This is not a coincidence.

The combinatorial shortcut

Any path from top-left to bottom-right in an $m \times n$ grid consists of exactly (m - 1) down-moves and (n - 1) right-moves, for a total of (m + n - 2) moves. The number of distinct orderings of these moves is the binomial coefficient C(m + n - 2, m - 1). This gives an $O(\min(m, n))$ closed-form solution with no DP table needed. However, this shortcut only works when there are no obstacles. The moment the grid has blocked cells, you need the DP approach.

Handling obstacles

LeetCode 63 adds a complication: some cells are blocked. The modification is straightforward: if a cell is an obstacle, set dp[i][j] = 0, since no paths pass through it. Otherwise, the recurrence is the same. You also need to be careful with the base cases: if any cell in the first row is blocked, all cells to its right in the first row are also unreachable (since the only way to reach them was through the blocked cell).

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1:
        return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for j in range(1, n):
        dp[0][j] = 0 if grid[0][j] == 1 else dp[0][j-1]
    for i in range(1, m):
        dp[i][0] = 0 if grid[i][0] == 1 else dp[i-1][0]
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

The key insight is that setting blocked cells to zero causes their contributions to propagate correctly through the rest of the table. Any path that would have passed through a blocked cell simply is not counted.

From counting to optimization: minimum path sum

With LeetCode 64, each cell has a cost, and you want to find the path from top-left to bottom-right with the minimum total cost. The structure is almost identical, but instead of adding path counts, you take the minimum:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Let us trace through a small example. Consider this $3 \times 3$ grid of costs:

1  3  1
1  5  1
4  2  1

Fill in the DP table. First row: 1, 4, 5 (cumulative sums, since you can only come from the left). First column: 1, 2, 6. Then:

• dp[1][1] = 5 + min(4, 2) = 7
• dp[1][2] = 1 + min(5, 7) = 6
• dp[2][1] = 2 + min(7, 6) = 8
• dp[2][2] = 1 + min(6, 8) = 7

The minimum path sum is 7, corresponding to the path 1 -> 3 -> 1 -> 1 -> 1. Notice how the DP naturally finds this without ever explicitly constructing a path. It just propagates the best cost to each cell.

Space optimization

Look at the recurrence: dp[i][j] depends only on dp[i-1][j] (directly above) and dp[i][j-1] (directly left). That means when computing row i, you only need the values from row i-1. You can use a single 1D array of length n, updating it in place as you process each row:

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[j] = grid[0][0]
            elif i == 0:
                dp[j] = dp[j-1] + grid[i][j]
            elif j == 0:
                dp[j] = dp[j] + grid[i][j]
            else:
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
    return dp[n - 1]

When you read dp[j] before updating it, it still holds the value from the previous row, that is dp[i-1][j], the "above" value. After you update dp[j-1] in the current iteration, it holds the current row's value, that is dp[i][j-1], the "left" value. The single array naturally holds exactly what you need. This reduces space from $O(m \cdot n)$ to $O(n)$.

Dungeon Game: when you must go backwards

LeetCode 174 presents a twist that breaks the standard top-left-to-bottom-right approach. A knight starts at the top-left of a grid and must reach the bottom-right (the princess). Each cell modifies the knight's health: positive values heal, negative values deal damage. The knight dies if health ever drops to zero or below. What is the minimum starting health needed to survive the journey?

The natural instinct is to do DP from top-left to bottom-right, tracking the minimum health along the path. But this fails. The problem is that maximizing health at an intermediate cell does not guarantee survival for the rest of the path. A path might accumulate a lot of health early but then hit a devastating cell near the end. You need to know what is coming after each cell to decide how much health you need at that cell.

The solution is to work backwards, from bottom-right to top-left. Define dp[i][j] as the minimum health needed when entering cell (i, j) to guarantee survival through the rest of the path. At the bottom-right cell, you need at least 1 - dungeon[m-1][n-1] health (or 1 if the cell is non-negative). From any other cell, you will move either right or down, so you need enough health to survive the current cell and still have dp[i+1][j] or dp[i][j+1] health remaining, whichever is smaller:

def calculateMinimumHP(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if i == m - 1 and j == n - 1:
                dp[i][j] = max(1, 1 - dungeon[i][j])
            elif i == m - 1:
                dp[i][j] = max(1, dp[i][j+1] - dungeon[i][j])
            elif j == n - 1:
                dp[i][j] = max(1, dp[i+1][j] - dungeon[i][j])
            else:
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
    return dp[0][0]

The max(1, ...) ensures health never drops below 1: the knight must always be alive. The min chooses the direction requiring less future health. This reverse DP is necessary because the quantity being optimized (minimum starting health) depends on the suffix of the path, not the prefix.

This is an important lesson: not all grid DP problems go from top-left to bottom-right. When the quantity you need to compute at a cell depends on what happens after that cell, you must reverse the direction.

Triangle

The triangle problem (LeetCode 120) is a grid DP variant where the grid is triangular. You start at the top of a triangle and move to an adjacent number in the row below. Find the minimum path sum from top to bottom.

Working bottom-up is cleanest. Start from the bottom row and move upward. For each cell, add the minimum of the two cells below it:

def minimumTotal(triangle):
    dp = triangle[-1][:]  # start with the bottom row
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    return dp[0]

This uses $O(n)$ space (just one row) and avoids the boundary-case headaches of a top-down approach, where you would need to handle the edges of each row differently. It is a nice example of how choosing the right direction of DP can simplify the code.

Minimum falling path sum

A gentle variant is LeetCode 931. Given an $n \times n$ matrix, find the path from any cell in the first row to any cell in the last row with the minimum sum. From cell (i, j) you can move to (i+1, j-1), (i+1, j), or (i+1, j+1): three choices instead of two.

Process row by row. For each cell, take the minimum of the three cells above it (clamping at the edges) and add the current value:

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]
    for i in range(1, n):
        new_dp = [0] * n
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            new_dp[j] = matrix[i][j] + best
        dp = new_dp
    return min(dp)

The answer is min(dp) over the last row, since you can end at any column. This is the standard row-by-row DP pattern with a slightly wider dependency footprint. Note that you need a separate new_dp array (or process carefully) because each cell depends on dp[j+1], which you have not yet overwritten, unlike minimum path sum where dependencies only point left and above.

Maximal square

LeetCode 221 asks for the area of the largest square containing only 1s in a binary matrix. At first glance this seems like a search problem, but it has an elegant DP formulation.

Define dp[i][j] as the side length of the largest all-1 square whose bottom-right corner is at (i, j). If matrix[i][j] is 0, then dp[i][j] = 0. Otherwise, dp[i][j] is constrained by the squares ending at the cell above, the cell to the left, and the cell diagonally above-left:

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

The intuition: to extend a square to side length $k$ at (i, j), you need a square of side $k-1$ ending at each of the three neighbors. If any of them is smaller, that is the bottleneck.

def maximalSquare(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    best = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == "1":
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                best = max(best, dp[i][j])
    return best * best

The answer is best * best because the problem asks for the area, not the side length. This runs in $O(m \cdot n)$ time and can be space-optimized to $O(n)$ with a rolling row, though you need to save the diagonal value before overwriting it.

Longest increasing path in a matrix

LeetCode 329 breaks the right-and-down movement restriction entirely. From any cell, you can move in all four directions, but only to a neighbor with a strictly larger value. Find the length of the longest increasing path.

This is not standard bottom-up DP because the grid does not have a clean row-by-row processing order. Instead, use DFS with memoization. The strictly-increasing constraint guarantees no cycles, so memoization is safe:

def longestIncreasingPath(matrix):
    m, n = len(matrix), len(matrix[0])
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        best = 1
        for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                best = max(best, 1 + dfs(ni, nj))
        memo[(i, j)] = best
        return best
    return max(dfs(i, j) for i in range(m) for j in range(n))

Each cell is computed at most once and stored in memo, so the total work is $O(m \cdot n)$. The key insight is that the strictly-increasing constraint creates a DAG over the grid cells. Memoized DFS is equivalent to DP on this DAG. It just discovers the topological order implicitly through recursion rather than requiring you to sort cells by value first.

Cherry pickup: two agents on one grid

LeetCode 741 introduces a fundamentally different structure. You must travel from (0, 0) to (n-1, n-1) and back, collecting cherries. Each cherry can only be picked once. The return trip is equivalent to sending two agents simultaneously from (0, 0) to (n-1, n-1), both moving only right or down.

Model the two agents with positions (r1, c1) and (r2, c2). Since both agents take the same number of steps and each step increments row + column by 1, we have r1 + c1 = r2 + c2 = t at step $t$. This means c2 = r1 + c1 - r2, so the state is just (r1, c1, r2), three dimensions instead of four:

def cherryPickup(grid):
    n = len(grid)
    memo = {}
    def dp(r1, c1, r2):
        c2 = r1 + c1 - r2
        if (r1 >= n or c1 >= n or r2 >= n or c2 >= n
                or grid[r1][c1] == -1 or grid[r2][c2] == -1):
            return float("-inf")
        if r1 == n - 1 and c1 == n - 1:
            return grid[r1][c1]
        if (r1, c1, r2) in memo:
            return memo[(r1, c1, r2)]
        cherries = grid[r1][c1]
        if r1 != r2 or c1 != c2:
            cherries += grid[r2][c2]
        # both agents move: right/right, right/down, down/right, down/down
        cherries += max(dp(r1, c1+1, r2),
                        dp(r1, c1+1, r2+1),
                        dp(r1+1, c1, r2),
                        dp(r1+1, c1, r2+1))
        memo[(r1, c1, r2)] = cherries
        return cherries
    return max(0, dp(0, 0, 0))

The double-counting guard if r1 != r2 or c1 != c2 is essential: when both agents occupy the same cell, count the cherry only once. The max(0, ...) handles the case where no valid path exists (all paths blocked by thorns). This runs in $O(n^3)$ time and space.

Complexity

For an $m \times n$ grid, both counting and optimization problems run in $O(m \cdot n)$ time. You visit each cell once and do $O(1)$ work per cell. Space is $O(m \cdot n)$ for the full table, or $O(n)$ with the rolling-row optimization. These bounds are optimal since the input itself is size $m \times n$.

Recognizing this pattern

You're probably looking at grid 2D path DP when:

• The input is an explicit $m \times n$ grid and you must travel from one corner (or edge) to another.
• Movement is restricted to a few directions, usually right/down, so each cell has a small set of predecessors.
• The question is count the paths, minimize/maximize cost along the path, or can we reach the goal.
• There's no branching cost-vs-distance tradeoff that would require Dijkstra or BFS. The DAG ordering is implicit in the directions.

Common templates:

• Path counting: dp[i][j] = dp[i-1][j] + dp[i][j-1] for ways to reach (i, j). Example: Unique Paths.
• Min / max path cost: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Example: Minimum Path Sum.
• Reverse-direction DP: fill from goal back to start when the constraint depends on future state. Example: Dungeon Game.
• Triangle / variable-width grid: same recurrence but the neighbor set changes by row. Example: Triangle.
• Two simultaneous walks: extend to dp[r1][c1][r2] to track two paths sharing the grid. Example: Cherry Pickup.