Minimum Path Sum: Grid DP from Top-Left to Bottom-Right

You have a grid filled with non-negative numbers. Starting from the top-left corner, you can only move right or down. Find the path to the bottom-right corner that minimizes the total sum of cells along the way.

This is LeetCode 64: Minimum Path Sum, and it is one of the best problems for solidifying your understanding of grid DP. If you have already solved Unique Paths, you already know how to fill a 2D table cell by cell. This problem adds one twist: instead of counting paths, you are picking the cheapest one.

Why this problem matters

Minimum path sum shows up constantly in interviews because it tests whether you truly understand 2D DP or just memorized Unique Paths. The structure is identical (fill a grid from top-left to bottom-right, each cell depends on the cell above and to the left), but the transition changes from addition to a min operation. That small change is the difference between counting and optimizing, and optimizing is what most real-world DP problems ask you to do.

Once you see how to swap + for min in the recurrence, every other grid optimization problem (dungeon game, cherry pickup, triangle) follows the same idea. The minimum path sum pattern is the bridge between counting grid DP and optimization grid DP.

Starting with recursion

Think about the cell at position (r, c). You could have arrived from (r-1, c) (the cell above) or (r, c-1) (the cell to the left). The minimum cost to reach (r, c) is the cost of the cell itself plus whichever neighbor has the smaller accumulated cost.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])

    def helper(r, c):
        if r == 0 and c == 0:
            return grid[0][0]
        if r < 0 or c < 0:
            return float("inf")
        return grid[r][c] + min(helper(r - 1, c), helper(r, c - 1))

    return helper(rows - 1, cols - 1)

The base case: (0, 0) costs just grid[0][0]. Out-of-bounds positions return infinity so they never win the min. Everything else picks the cheaper of two neighbors and adds the current cell's cost.

This works, but it is painfully slow. Each call branches into two more, and the tree grows exponentially. For a 20x20 grid, you would be waiting a while. The time complexity is roughly O(2^(m+n)).

Adding memoization (top-down DP)

Cache each subproblem so you never compute it twice.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    memo = {}

    def helper(r, c):
        if r == 0 and c == 0:
            return grid[0][0]
        if r < 0 or c < 0:
            return float("inf")
        if (r, c) in memo:
            return memo[(r, c)]
        memo[(r, c)] = grid[r][c] + min(helper(r - 1, c), helper(r, c - 1))
        return memo[(r, c)]

    return helper(rows - 1, cols - 1)

Now each of the m * n cells is solved once. Time drops to O(m * n). Space is O(m * n) for the memo dictionary plus the recursion stack. Much better, but we can clean it up.

Building the 2D DP table (bottom-up)

Instead of recursing backwards from the destination, build the table forward from the top-left corner. Define dp[r][c] as the minimum cost to reach cell (r, c).

The recurrence:

• dp[0][0] = grid[0][0]
• First row: dp[0][c] = dp[0][c-1] + grid[0][c] (can only come from the left)
• First column: dp[r][0] = dp[r-1][0] + grid[r][0] (can only come from above)
• Everything else: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])

Let's trace through the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]]:

Each cell takes the current cost plus the minimum of the cell above and the cell to the left. The answer sits in the bottom-right corner: 7.

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

    dp[0][0] = grid[0][0]

    # First row
    for c in range(1, cols):
        dp[0][c] = dp[0][c - 1] + grid[0][c]

    # First column
    for r in range(1, rows):
        dp[r][0] = dp[r - 1][0] + grid[r][0]

    # Fill the rest
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])

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

Time: O(m * n). Every cell is visited exactly once.

Space: O(m * n). We store the full 2D table.

No recursion, no call stack, no hash map overhead. Just a nested loop filling cells from top-left to bottom-right. But we can still trim the space.

Optimizing to O(n) space

Look at the recurrence: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]). Each cell only depends on the cell above (previous row, same column) and the cell to the left (current row, previous column). We never look back further than one row.

That means a single 1D array of length n is enough. Before we update dp[c], its current value is the "from above" contribution (left over from the previous row). After we update dp[c-1], that value is the "from left" contribution for the current row.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [0] * cols

    # First row
    dp[0] = grid[0][0]
    for c in range(1, cols):
        dp[c] = dp[c - 1] + grid[0][c]

    # Remaining rows
    for r in range(1, rows):
        dp[0] = dp[0] + grid[r][0]
        for c in range(1, cols):
            dp[c] = grid[r][c] + min(dp[c], dp[c - 1])

    return dp[cols - 1]

Same O(m * n) time, but now O(n) space. One row instead of an entire grid.

Let's trace this for our 3x3 example:

• After row 0: [1, 4, 5] (prefix sums of the first row)
• Row 1: dp[0] = 1 + 1 = 2. dp[1] = 5 + min(4, 2) = 7. dp[2] = 1 + min(5, 7) = 6. Row: [2, 7, 6]
• Row 2: dp[0] = 2 + 4 = 6. dp[1] = 2 + min(7, 6) = 8. dp[2] = 1 + min(6, 8) = 7. Row: [6, 8, 7]
• Return dp[2] = 7

In-place modification (O(1) extra space)

If the problem allows you to modify the input grid, you can skip the separate DP table entirely and write the accumulated costs directly into grid.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])

    for c in range(1, cols):
        grid[0][c] += grid[0][c - 1]

    for r in range(1, rows):
        grid[r][0] += grid[r - 1][0]

    for r in range(1, rows):
        for c in range(1, cols):
            grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])

    return grid[rows - 1][cols - 1]

Same O(m * n) time, O(1) extra space. The downside is that you destroy the original grid. In an interview, mention this trade-off and ask the interviewer whether mutating the input is acceptable.

Complexity analysis

The progression is the same four-step pipeline you saw in Climbing Stairs and Unique Paths:

1. Write the recursive solution to get the logic right.
2. Add memoization to eliminate redundant work.
3. Convert to bottom-up to remove recursion overhead.
4. Optimize space by keeping only what the recurrence needs.

Edge cases to watch for

• 1x1 grid: return grid[0][0]. There is nowhere to go.
• Single row (1xn): the only path is straight right. Sum the entire row.
• Single column (mx1): the only path is straight down. Sum the entire column.
• All zeros: the minimum path sum is 0 regardless of grid size.
• Large values: costs can be up to 200 and the grid up to 200x200, so the maximum possible sum is 40,000. No overflow concerns with standard integers.

The building blocks

This problem is built on one reusable pattern: 2D grid DP. It is the same building block behind Unique Paths, but the transition function changes from counting (+) to optimizing (min).

The pattern has a specific shape:

• State: dp[r][c] represents the optimal answer for the subproblem at position (r, c)
• Transition: dp[r][c] combines values from adjacent cells using min (or max, depending on the problem) plus the current cell's cost
• Base cases: first row and first column have only one direction to come from, so they accumulate in a straight line
• Space optimization: if the recurrence only looks at the current and previous row, collapse to a 1D array

The same building block appears in many other problems:

• Unique Paths (LeetCode 62): same grid structure, but counting instead of minimizing. dp[r][c] = dp[r-1][c] + dp[r][c-1].
• Unique Paths II (LeetCode 63): adds obstacles. Blocked cells get dp[r][c] = 0.
• Triangle (LeetCode 120): a triangular grid instead of rectangular. Each cell depends on two cells from the row above.
• Dungeon Game (LeetCode 174): similar grid traversal, but you fill from bottom-right to top-left because the constraint is on the path minimum, not the path sum.

Once you internalize 2D grid DP as a building block, these problems feel like variations on a theme rather than separate challenges.

From understanding to recall

You have traced through the full DP table, seen the space optimization, and understand why min replaces + compared to Unique Paths. But understanding is not the same as producing this from scratch under pressure.

In an interview, you need to quickly identify that this is a grid DP problem, write the recurrence with min, handle the base cases for the first row and first column, and implement the space-optimized version if asked. That fluency comes from practice, not just reading.

Spaced repetition closes the gap. You revisit this problem at increasing intervals, each time writing the table setup and space optimization from memory. After a few reps, the grid DP pattern is automatic. You see a grid with costs and your hands know what to type.

The 2D grid DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Unique Paths - The counting version of grid DP, and the natural predecessor to this problem
• Climbing Stairs - Your first DP problem, teaching the recursion-to-table pipeline in 1D before you extend it to 2D