2D DP
How 2D DP works
Why it matters
Warehouse robots, game boards, and lattice models often need the number of routes through a rectangular space. Enumerating routes becomes exponential because many different histories arrive at the same cell. The total for an m × n grid must be computed by processing only its m · n positions, not every complete path.
Example
Unique Paths
A robot on an m x n grid can only move down or right. Return how many paths go from (0,0) to (m-1,n-1).
- Input
- m = 3, n = 4
- Output
- 10
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Unique Paths
m = 3, n = 4→10
The baseline, Count every path recursively, is O(2^(m + n)) · O(m + n). The better model below keeps this exact input and removes that bottleneck.
For a 3 × 4 grid, brute recursion reaches cells such as (1, 1) through many paths and recounts their suffixes. Fill each of the 12 cells once from its upper and left totals; the bottom-right value becomes 10.
For m = 3 and n = 4, every cell in the top row and left column is 1 because only one sequence of right or down moves reaches it. At (1, 1), add 1 from above and 1 from the left to get 2.
Continue row by row: the second row becomes [1, 2, 3, 4], and the third becomes [1, 3, 6, 10]. Each path into a cell ends with a move from above or the left, and those two groups do not overlap, so their counts add.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.