Pattern Recognition Drill
Medium 2-D Dynamic Programming
The Problem
Given an m×n grid, count the number of unique paths from top-left to bottom-right (only move right or down).
What approach would you use?
Think about it before scrolling down.
1D DP row: dp[j] += dp[j-1]. O(m*n) time, O(n) space.
C(m+n-2, m-1) — direct combinatorial formula. O(m+n) time.
Common Trap
The combinatorial approach is O(1) space but watch for integer overflow in other languages.