Dynamic Programming · LC #62
Unique Paths
A robot on an m×n grid can only move right or down. The number of unique paths equals the sum of paths from the cell above and the cell to the left; solvable via DP in O(m·n) or combinatorially in O(1).
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
A robot is on the top-left corner of an `m x n` grid. It can only move right or down. Count how many unique paths reach the bottom-right corner.
Sample I/O
Input: m=3, n=7 Output: 28 Input: m=3, n=2 Output: 3
Intuition
How to Think About It
Intuition
Every path from top-left to bottom-right makes exactly (m-1) down moves and (n-1) right moves in some order. The count is the binomial coefficient C(m+n-2, m-1), or equivalently each cell's value equals the sum of its top and left neighbours.
Core Concept
1D rolling DP: initialise `dp` of length n to all 1s (first row). For each subsequent row, update left-to-right: `dp[j] += dp[j-1]`. After m-1 row updates, `dp[n-1]` holds the answer.
When to use
Grid path-counting, probability calculations on grids, or any problem reducible to counting paths in a DAG with two in-edges per node.
When NOT to use
When obstacles exist (use Unique Paths II - LC 63). When paths have costs (use Dijkstra or DP with weights). When movement is not restricted to right/down.
Key Insights
What to Know Cold
- The first row and first column are always all 1s - only one way to reach any cell in them.
- Rolling 1D DP avoids allocating a full m×n matrix.
- Combinatorial closed form: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!) - O(1) space and time.
- Symmetry: uniquePaths(m, n) == uniquePaths(n, m) - always iterate over the larger dimension as the outer loop for cache efficiency.
- This is the Pascal's triangle generation pattern applied to a 2D grid.
1 example
Worked Examples
3×7 grid path count
Robot must reach bottom-right of a 3-row, 7-column grid.
1D rolling DP: update each row in-place from left to right.
Output: 28
Classic grid DP that introduces the rolling-array space optimisation; used as a warm-up for harder grid problems like Minimum Path Sum and Dungeon Game.