0

Minimum Path Sum

Medium

Movement is restricted to right and down, which fixes the dependency order: every cell needs the one above and the one to its left.

griddependency order
TimeO(rows * cols)
SpaceO(cols)
InputRows of numbers separated by spaces
col 0
col 1
col 2
row 0
10
30
10
row 1
10
50
10
row 2
40
20
10
cell being filledcells it readsreconstructed answer

Each cell holds the cheapest cost of reaching it from the top left.

1 / 11
dp[0][0] = grid[0][0]
for each cell in row-major order:
best = min(dp[r-1][c], dp[r][c-1])
dp[r][c] = grid[r][c] + best
answer = dp[R-1][C-1]
Why it matters

Unique paths, maximal square and dungeon game are the same walk with different combine rules.

Practise this
Minimum Path SumMUnique PathsMMaximal SquareMTriangleM
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Kadane (Maximum Subarray)
O(n)
Memoisation vs Brute Force
O(2^n) naive, O(n) memoised
0/1 Knapsack
O(n * W)
Longest Common Subsequence
O(n * m)
Coin Change
O(coins * amount)
Longest Increasing Subsequence
O(n log n)
Edit Distance
O(n * m)
Next visualiser
Edit Distance