Unique Paths
Count paths from top-left to bottom-right using only right and down moves.
Why does this pattern fit?
Restate the exact job
Count paths from top-left to bottom-right using only right and down moves.
Ways to a cell equal ways from above plus ways from left.
O(mn) time · O(n) space
Resetting the first column to zero destroys the only path along the edge.
How to solve Unique Paths
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Count paths from top-left to bottom-right using only right and down moves.
Why Dynamic programming fits
Ways to a cell equal ways from above plus ways from left.
State to maintain
One row of path counts.
Transition
Scan rows; update each cell as current (from above) + left neighbor.
Time and space
O(mn) time · O(n) space
Counterexample to the tempting mistake
Resetting the first column to zero destroys the only path along the edge.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.