MediumArrayDynamic ProgrammingMatrix

Minimum Path Sum

1 approach, code in every language

You are given an m x n grid filled with non-negative numbers. Starting from the top-left cell you want to reach the bottom-right cell, and on each move you may travel only one cell to the right or one cell down.

Return the smallest possible sum of all numbers along a valid path from the top-left corner to the bottom-right corner.

Example 1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Output: 7

The route 1 -> 3 -> 1 -> 1 -> 1 accumulates the minimum total of 7.

Example 2

Input: grid = [[1,2,3],[4,5,6]]

Output: 12

The path 1 -> 2 -> 3 -> 6 sums to 12, the least achievable for this grid.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

In-Place Grid DP

Overwrite each cell with the cheapest cost to reach it from the top-left, reusing the grid as the DP table.

Loading animation…

Intuition

The cheapest way to stand on cell (i, j) must have arrived from either the cell above or the cell to the left, whichever costs less, plus the value already sitting in (i, j). That yields dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). The top row and left column are special because they have a single predecessor, so their costs are just running prefix sums. Since each cell only depends on neighbors we have already finalized when scanning row by row, we can write the accumulated cost straight back into the grid and avoid any extra allocation. Processing left to right, top to bottom guarantees both dependencies are ready before we use them. The bottom-right cell ends up holding the minimum total path sum.

Algorithm walkthrough

1Read the dimensions m and n from the grid.
2Iterate rows top to bottom and, within each row, columns left to right.
3Skip the origin (0, 0): its cost is already its own value.
4For the first row (i == 0) only the left neighbor exists, so add grid[i][j-1]; for the first column (j == 0) only the top neighbor exists, so add grid[i-1][j].
5For every interior cell add the smaller of the top and left accumulated costs: grid[i][j] += min(grid[i-1][j], grid[i][j-1]).
6Return grid[m-1][n-1], the minimized total path sum at the destination.

Implementation

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        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]

Time

O(m * n)

Space

O(1)

Each cell is visited exactly once and the grid itself stores the DP state, so no auxiliary structure is allocated. If mutating the input is undesirable, a separate O(n) row can be used instead.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Cheapest Bay Route is our own problem on the technique behind Minimum Path Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free