Minimum Path Sum

Medium#642d table

A grid holds a cost in every cell. Go from the top-left corner to the bottom-right one, stepping only right or down, and pay for every cell you stand on, both corners included. Find the smallest total. Our example: [3, 1, 5, 1], [2, 6, 4, 2], [1, 1, 3, 2], the answer is 12.

64 Minimum Path SumWalkthrough · 1×

Example: a 3 × 4 grid. The first step right costs only 1, but the cheapest path goes down the left column; the last cell takes 10 from the left over 12 from above.

0123012+3+1+5+1+2+6+4+2+1+1+3+2
not filled yet: +its costcheapest sum into this cellthis stepread fromthe cheapest path

An empty table the size of the grid; each cell shows its cost until it is filled

01/40
restart · back · play · step
Speed
1function minPathSum(grid):
2 dp = table of the grid's size
3 for r from 0 to rows - 1:
4 for c from 0 to cols - 1:
5 if r == 0 and c == 0:
6 dp[r][c] = grid[r][c]
7 continue
8 up = dp[r - 1][c] if r > 0 else infinity
9 left = dp[r][c - 1] if c > 0 else infinity
10 dp[r][c] = min(up, left) + grid[r][c]
11 return dp[rows - 1][cols - 1]
state
dp
[[–, –, –, –], [–, –, –, –], [–, –, –, –]]
r
–
c
–
up
–
left
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every path into (r, c) arrives from (r - 1, c) or from (r, c - 1). The cheapest one is the cheapest way into the better of those two plus the cost of (r, c), so min of two finished cells is enough.
  2. A cell on the top row or the left column has one way in; the missing side counts as ∞, so min always takes the real one.
  3. Picking the cheaper next cell at each step is not enough: here the 1 to the right of the start leads to a total of 14, while the table finds 12 by going down first.

Complexity

Time O(m × n): each cell is one min and one addition. Memory O(m × n) for the table; a cell reads only its row and the row above, so one row of n cells is enough, or the grid itself can be overwritten.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.