DSA Tracker

Visualize

Minimum Path Sum

dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])

time O(m * n)space O(m * n)

A cell can only be entered from directly above or directly to its left — those are the only two moves allowed. So the cheapest way to reach any cell is its own cost plus whichever of those two neighbors was cheaper to reach. The top row and left column each have only one possible predecessor, so they fill in as running sums; every interior cell then picks the smaller of its two already-known neighbors.

Details

Animated on: grid = [[1,3,1],[1,5,1],[4,2,1]] — moving only right or down from top-left, find the path to bottom-right that minimizes the sum of the numbers it passes through.

Problem:Minimum Path SumMedium

dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])

step 1 / 11

dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]) — only right/down moves reach a cell

A 3x3 grid of costs. Only right and down moves are allowed, so every cell is reached from exactly one of two neighbors — the cell above or the cell to its left.

Pseudocode
1FUNCTION minPathSum(grid):
2  dp[0][0] <- grid[0][0]
3  FOR c FROM 1 TO n-1:
4    dp[0][c] <- dp[0][c-1] + grid[0][c]
5  FOR r FROM 1 TO m-1:
6    dp[r][0] <- dp[r-1][0] + grid[r][0]
7  FOR r FROM 1 TO m-1:
8    FOR c FROM 1 TO n-1:
9      dp[r][c] <- grid[r][c] + MIN(dp[r-1][c], dp[r][c-1])
10  RETURN dp[m-1][n-1]

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. A 3x3 grid of costs. Only right and down moves are allowed, so every cell is reached from exactly one of two neighbors — the cell above or the cell to its left.
  2. Top-left corner has no predecessor — dp[0][0] = grid[0][0] = 1, the starting cost.
  3. Top row: (0,1) can only arrive from the left. dp = grid(3) + left(1) = 4.
  4. Top row: (0,2) can only arrive from the left. dp = grid(1) + left(4) = 5.
  5. Left column: (1,0) can only arrive from above. dp = grid(1) + up(1) = 2.
  6. (1,1): up(4) vs left(2) — left is cheaper, so dp = grid(5) + 2 = 7. The pricier neighbor is dropped; it can never be part of the minimum path.
  7. (1,2): up(5) vs left(7) — up is cheaper, so dp = grid(1) + 5 = 6. The pricier neighbor is dropped; it can never be part of the minimum path.
  8. Left column: (2,0) can only arrive from above. dp = grid(4) + up(2) = 6.
  9. (2,1): up(7) vs left(6) — left is cheaper, so dp = grid(2) + 6 = 8. The pricier neighbor is dropped; it can never be part of the minimum path.
  10. (2,2): up(6) vs left(8) — up is cheaper, so dp = grid(1) + 6 = 7. The pricier neighbor is dropped; it can never be part of the minimum path.
  11. dp[2][2] = 7 — the minimum-sum path from top-left to bottom-right costs 7.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Path Sum in the editorAll Dynamic Programming problemsBack to roadmap