← DSA Atlas
Dedicated problem page · #64

Minimum Path Sum

MediumTwo-Dimensional Dynamic ProgrammingGrid path DP (right/down accumulation)2D dynamic programming on a grid
Solve on LeetCode ↗
64
MediumTwo-Dimensional Dynamic Programming2D dynamic programming on a gridGrid path DP (right/down accumulation)

Minimum Path Sum

Given an m x n grid filled with non-negative numbers, find a path from the top-left cell to the bottom-right cell that minimizes the sum of numbers along the path. You may only move either right or down at any step. Return that minimum sum.

Open official problem prompt ↗
In plain English

Compute the smallest possible sum of values collected while walking from the top-left corner to the bottom-right corner, moving only right or down.

Picture it like this

Think of a toll-road map where every intersection charges a fee. From home you can only drive east or south to work. The cheapest fare to any intersection is its own toll plus the cheaper of the two roads feeding into it.

Example
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
Why
The path 1 -> 3 -> 1 -> 1 -> 1 sums to 7, which is smaller than any other right/down path.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
Pattern lesson

See the pattern, then code

Grid path DP (right/down accumulation)
Recognition clue

You are asked for the minimum (or maximum) cost of a path through a grid with movement restricted to right and down. Each cell's best value depends only on the cell above and the cell to the left, which signals grid DP.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. The cheapest way to reach a cell is its own value plus the cheaper of the two ways to arrive: from above or from the left. Fill the grid in reading order so both predecessors are already solved.

New words, made simpleKnow these before the algorithm
State
A cell (i, j) whose value is the minimum cost to reach it from the start
Transition
The rule dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
In-place DP
Overwriting the input grid to store answers so no extra table is needed
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force recursion over all paths

Exponential because the same cells are recomputed along overlapping paths.

Recursively try every right/down path from (0,0) and keep the minimum sum.

Time O(2^(m+n))Space O(m+n)
Best choiceBottom-up grid DP

Each cell is solved once from already-solved neighbors; optimal in both time and space.

Fill each cell with its own value plus the cheaper predecessor, in reading order, reusing the grid itself.

Time O(m*n)Space O(1) extra
The rule we keep true

Invariant

When cell (i, j) is processed, grid[i][j] holds the true minimum path cost from (0,0) to (i,j), and its two predecessors (i-1,j) and (i,j-1) already hold their final values.

Why this is correct

Reasoning

Any path into (i,j) must pass through either the cell above or the cell to the left as its last step. Taking the minimum of those two optimal sub-answers and adding the current toll yields the optimum for (i,j); induction from the start cell proves the whole grid is correct.

The algorithm in three movesSay these aloud before coding
1Treat grid[i][j] as the minimum cost to reach that cell

row0 costs: 1, 4, 5

2The first row can only be reached from the left; the first column only from above

col0 costs: 1, 2, 6

3For every other cell add the min of the cell above and the cell to the left

grid[2][2] = 1 + min(7, 6) = 7

4Return the value stored in the bottom-right cell

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
31
12
13
54
15
46
27
18
1 · Readcells (0,1) and (0,2)
2 · AskHow cheaply can the top row be reached?
3 · Update staterow0 = [1, 4, 5]
4 · ResultOnly leftward arrival is possible, so values accumulate: 1, 1+3=4, 4+1=5
Key takeaway

The 3x3 grid; highlighted cells trace the optimal 1->3->1->1->1 path.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-6Skip the origin

    The start cell already holds its own cost; nothing is added to it.

  2. 2
    Lines 7-10Handle the borders

    First row and first column have only one legal predecessor, so they accumulate in a single direction.

  3. 3
    Lines 11-12Interior transition

    Every inner cell adds the cheaper of the cell above and the cell to the left.

  4. 4
    Lines 13Return the corner

    The bottom-right cell now stores the global minimum path sum.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single cell grid returns that cell's value
  • A single row or single column has exactly one path
  • Zeros in the grid are valid and do not shortcut the path rules
!

Common beginner mistakes

  • Forgetting that borders have only one predecessor and indexing out of bounds
  • Trying to also allow up/left moves, which this problem forbids
  • Assuming a greedy step-by-step choice is optimal; only full DP guarantees the minimum
Check your understanding

Why can we safely overwrite the input grid instead of allocating a separate DP table?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#44Wildcard MatchingGlob-matching grid DP#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles