LeetCode 62 · 2-D DP · concept: dynamic-programming
Problem
A robot at the top-left of an m × n grid moves only right or down. How many unique paths to the bottom-right?
The recurrence
Each cell is reached from above or from the left, so the number of paths to (r, c) is the sum of paths to those two: dp[r][c] = dp[r-1][c] + dp[r][c-1]. The first row and column are all 1 (one straight-line path).
Approach — 1-D rolling row (optimal space)
The full grid DP is O(m·n) space, but each row only needs the row above, so a single array suffices — row[c] += row[c-1] folds in the “from the left” term while row[c] already holds “from above.”
def uniquePaths(m, n):
row = [1] * n # top row: one path to each cell
for _ in range(1, m):
for c in range(1, n):
row[c] += row[c - 1] # from above (old row[c]) + from left (row[c-1])
return row[-1]Time O(m·n), space O(n).
The 2-D DP starting point
This is the simplest grid DP: state is (row, col), and the answer combines a fixed set of neighbor cells (up + left). Once you can read a recurrence off “which adjacent cells lead here,” most grid DP follows. (There’s also a closed-form binomial C(m+n-2, m-1), since every path is a fixed arrangement of moves.)
Key insight
Grid path-counting → dp[r][c] = dp[r-1][c] + dp[r][c-1], reducible to one rolling row. The template for 2-D DP where each state depends on a small window of neighbors — the foundation for the harder grid/sequence DPs.
Related
- concept: dynamic-programming
- next: Longest Common Subsequence
Software engineering
Infrastructure & security
Computer science
Hardware & engineering