DPDynamic Programming

Grid DP (min path sum)

State is a cell (r, c); the answer for a cell comes from its allowed predecessor cells (usually up and left).

Grid — One row of numbers per line, up to 5×5 — e.g. "1 3 1 / 1 5 1 / 4 2 1"

1→1

dp (min sum to reach cell)

0	1	2	3
1

1/13Each cell shows "value→dp". Moving only right or down, the cheapest way to reach the start is its own value, 1.

Cell being filledDependency (up / left)ComputedOptimal path

PseudocodeLearn Grid DP →

1dp[0][0] = g[0][0]
2for each cell (r, c) in row-major order:
3  up = dp[r-1][c] if r > 0 else ∞
4  left = dp[r][c-1] if c > 0 else ∞
5  dp[r][c] = g[r][c] + min(up, left)
6return dp[R-1][C-1]; trace back to reconstruct path

Variables

Complexity

worst O(rows × cols)

space O(rows × cols), reducible to O(cols)

Speed