DP Grid Traversal: Unique Paths, Min Path Sum, Dungeon Game & Cherry Pickup

Grid DP problems are among the most common interview questions. The grid gives you a natural 2D state space, and the transitions are usually just “from the cell above” or “from the cell to the left.” This post covers the five most important grid DP patterns.

1. Unique Paths

Problem: A robot starts at the top-left corner of an m x n grid and can only move right or down. How many unique paths exist to reach the bottom-right corner? (LeetCode 62)

The Recurrence

dp[i][j] = number of ways to reach cell (i, j).

• Base case: dp[0][j] = 1 for all j, dp[i][0] = 1 for all i
• Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]

def unique_paths(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]

Time: O(m * n) | Space: O(m * n)

Space-Optimised to O(n)

Since each row only depends on the previous row, we can use a single array:

def unique_paths_optimised(m, n):
    dp = [1] * n

    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]

    return dp[n - 1]

Math Solution: O(1)

The answer is the binomial coefficient C(m + n - 2, m - 1):

from math import comb

def unique_paths_math(m, n):
    return comb(m + n - 2, m - 1)

Unique Paths II (with Obstacles)

When some cells are blocked (LeetCode 63):

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1:
        return 0

    dp = [0] * n
    dp[0] = 1

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j - 1]

    return dp[n - 1]

---

2. Minimum Path Sum

Problem: Given an m x n grid filled with non-negative numbers, find a path from top-left to bottom-right that minimises the sum. You can only move right or down. (LeetCode 64)

The Recurrence

dp[i][j] = minimum cost to reach cell (i, j).

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n

    # First row: accumulate left to right
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]

    # Fill row by row
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
            #                         ^top     ^left

    return dp[n - 1]

Time: O(m * n) | Space: O(n)

In-Place Variant

If you are allowed to modify the input grid:

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

---

3. Dungeon Game

Problem: A knight starts at the top-left of a grid and must reach the bottom-right (the princess). Each cell adds or removes health. Find the minimum initial health needed to survive (health must always be >= 1). (LeetCode 174)

Why Forward DP Fails

In minimum path sum, you accumulate costs going forward. But in the dungeon game, a cell might give you +100 health, which only matters if you survive to reach it. You need to know future requirements.

Reverse DP: Bottom-Right to Top-Left

dp[i][j] = minimum health needed when entering cell (i, j).

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Sentinel values: everything outside the grid needs infinite health
    for i in range(m + 1):
        dp[i][n] = float('inf')
    for j in range(n + 1):
        dp[m][j] = float('inf')

    # The cell just past the princess needs 1 health
    dp[m][n - 1] = 1
    dp[m - 1][n] = 1

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            min_health_needed = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = max(min_health_needed, 1)

    return dp[0][0]

Time: O(m * n) | Space: O(m * n), reducible to O(n)

Space-Optimised

def calculate_minimum_hp_opt(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [float('inf')] * (n + 1)
    dp[n - 1] = 1

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            dp[j] = max(min(dp[j], dp[j + 1]) - dungeon[i][j], 1)

    return dp[0]

---

4. Cherry Pickup

Problem: An n x n grid has cherries (1) and empty cells (0). You walk from (0,0) to (n-1,n-1) collecting cherries, then walk back. Cherries are collected once. Find the maximum cherries. (LeetCode 741)

The Key Insight

Instead of one round trip, simulate two people walking simultaneously from (0,0) to (n-1,n-1). Both take one step per turn (right or down). If they are on the same cell, count the cherry only once.

State: dp[r1][c1][r2]

Since both take the same number of steps, r1 + c1 = r2 + c2, so c2 = r1 + c1 - r2.

def cherry_pickup(grid):
    n = len(grid)
    memo = {}

    def dp(r1, c1, r2):
        c2 = r1 + c1 - r2
        # Out of bounds or thorns
        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')

        # Reached destination
        if r1 == n - 1 and c1 == n - 1:
            return grid[r1][c1]

        if (r1, c1, r2) in memo:
            return memo[(r1, c1, r2)]

        # Cherries from current cells
        cherries = grid[r1][c1]
        if r1 != r2 or c1 != c2:
            cherries += grid[r2][c2]

        # Four combinations of moves (right/down for each person)
        best = max(
            dp(r1 + 1, c1, r2 + 1),  # both down
            dp(r1 + 1, c1, r2),       # p1 down, p2 right
            dp(r1, c1 + 1, r2 + 1),   # p1 right, p2 down
            dp(r1, c1 + 1, r2),       # both right
        )

        result = cherries + best
        memo[(r1, c1, r2)] = result
        return result

    return max(0, dp(0, 0, 0))

Time: O(n^3) | Space: O(n^3)

Cherry Pickup II (Two Robots)

In the variant (LeetCode 1463), two robots start at the top row (columns 0 and n-1) and move down. Each can go down-left, down, or down-right.

def cherry_pickup_ii(grid):
    m, n = len(grid), len(grid[0])
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(row, c1, c2):
        if row == m:
            return 0

        cherries = grid[row][c1]
        if c1 != c2:
            cherries += grid[row][c2]

        best = 0
        for dc1 in (-1, 0, 1):
            for dc2 in (-1, 0, 1):
                nc1, nc2 = c1 + dc1, c2 + dc2
                if 0 <= nc1 < n and 0 <= nc2 < n:
                    best = max(best, dp(row + 1, nc1, nc2))

        return cherries + best

    return dp(0, 0, n - 1)

Time: O(m * n^2 * 9) | Space: O(m * n^2)

---

5. Maximum Falling Path Sum

Problem: Given an n x n matrix, find the maximum sum of a path that starts at any cell in the first row, moves to the next row choosing from the cell directly below, below-left, or below-right. (LeetCode 931)

def max_falling_path_sum(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 = max(best, dp[j - 1])
            if j < n - 1:
                best = max(best, dp[j + 1])
            new_dp[j] = matrix[i][j] + best
        dp = new_dp

    return max(dp)

Time: O(n^2) | Space: O(n)

Variant: Non-Adjacent Columns (LeetCode 1289)

The falling path cannot use the same column in adjacent rows. Track the top two maximums:

def max_falling_path_non_adjacent(grid):
    n = len(grid)
    # dp stores (best_value, best_col, second_best_value)
    prev = grid[0][:]

    for i in range(1, n):
        # Find top 2 from previous row
        first_val, first_col = max((prev[j], j) for j in range(n))
        second_val = max(prev[j] for j in range(n) if j != first_col) if n > 1 else float('-inf')

        curr = [0] * n
        for j in range(n):
            if j != first_col:
                curr[j] = grid[i][j] + first_val
            else:
                curr[j] = grid[i][j] + second_val
        prev = curr

    return max(prev)

Time: O(m * n) | Space: O(n)

---

Grid DP Patterns Summary

Pattern	Direction	Key Idea
Count paths	Top-left to bottom-right	Sum of top + left
Min/max cost	Top-left to bottom-right	Accumulate optimally
Min health	Bottom-right to top-left	Future requirements matter
Two paths	Simulate simultaneously	Extra dimension in state
Falling path	Row by row downward	Choose from 2-3 cells above

---

Common Mistakes

1. Wrong base cases: Forgetting to initialise the first row and first column separately.
2. Off-by-one with sentinels: When using (m+1) x (n+1) arrays, the sentinel values must be chosen carefully (infinity for min problems, 0 for count problems).
3. Not handling obstacles: Blocked cells must set dp[j] = 0 (for counting) or infinity (for min-cost).
4. Cherry double counting: When two paths are on the same cell, count the cherry only once.
5. Forgetting the reverse direction for dungeon game.

---

Practice Problems

Problem	Platform	Difficulty	Pattern
Unique Paths	LeetCode 62	Medium	Count paths
Unique Paths II	LeetCode 63	Medium	With obstacles
Minimum Path Sum	LeetCode 64	Medium	Min cost
Dungeon Game	LeetCode 174	Hard	Reverse DP
Cherry Pickup	LeetCode 741	Hard	Two paths
Cherry Pickup II	LeetCode 1463	Hard	Two robots
Minimum Falling Path Sum	LeetCode 931	Medium	Falling path
Minimum Falling Path Sum II	LeetCode 1289	Hard	Non-adjacent
Triangle	LeetCode 120	Medium	Bottom-up path
Maximal Square	LeetCode 221	Medium	Grid DP