Problem Statement

Minimum Path Sum

You are given a grid of numbers with m rows and n columns. Every number is zero or positive. You start in the top-left cell and want to reach the bottom-right cell. You can only step right or step down, never up or left. As you walk, you add up the numbers in the cells you land on. The goal is to find the path whose total is the smallest, and return that total. The trick is that the cheapest way to reach any cell depends only on how you got there, and there are just two ways in: from the cell directly above, or from the cell directly to the left. That repeating "answer for here is built from the answers next to here" is what we lean on. We will also reuse the grid itself to store our running answers, so we do not need extra space.

mediumDynamic ProgrammingMatrixDynamic ProgrammingTime: O(m * n) · Space: O(1)

Signals to notice

find path with minimum cost sum in gridcan only move right or downaccumulate costs

Brute force first

Try all paths. Each cell branches into right and down. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

DP: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Each cell's minimum cost comes from the cheaper of the cell above or to the left., and you can compress the memory down even further. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `grid=[[1,3,1],[1,5,1],[4,2,1]]`

Init m=3, n=3. Grid unchanged: [[1,3,1],[1,5,1],[4,2,1]]
First row prefix sums: grid[0][1]=3+1=4, grid[0][2]=1+4=5 -> row0=[1,4,5]
First col prefix sums: grid[1][0]=1+1=2, grid[2][0]=4+2=6 -> col0=[1,2,6]
i=1: grid[1][1]=5+min(4,2)=7; grid[1][2]=1+min(5,7)=6 -> row1=[2,7,6]
i=2: grid[2][1]=2+min(7,6)=8; grid[2][2]=1+min(6,8)=7 -> row2=[6,8,7]
Return grid[2][2]=7

What must stay true

You can only arrive from above or the left. The minimum cost to reach (i,j) is its own cost plus the cheaper of the two possible predecessors. No other path can be cheaper. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

function minPathSum(grid):
  for j in 1..n-1: grid[0][j] += grid[0][j-1]        # prefix-sum first row
  for i in 1..m-1: grid[i][0] += grid[i-1][0]        # prefix-sum first col
  for i in 1..m-1, for j in 1..n-1:
      grid[i][j] += min(grid[i-1][j], grid[i][j-1])  # cheaper predecessor
  return grid[m-1][n-1]

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not initializing the first row and column correctly — the first row can only come from the left, and the first column only from above. They have only one predecessor each. The fix is usually to return to the meaning of each move, not just the steps themselves.

Dynamic Programming Pattern