#62
Unique Paths
Medium 2D grid DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A robot at the top-left of an m × n grid moves only right or down. Count the paths to the bottom-right.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: paths from the top-left to the bottom-right moving right or down.
Why this works: paths to a cell = paths from above + paths from the left.
Example: 3 × 3 grid
row 0: 1 1 1row 1: 1 2 3row 2: 1 3 6 → 6
✦Hints open one at a time
Paths to a cell = paths to the cell above + paths to the cell on the left.
The first row and first column have exactly one path each.
↗Approach
Keep one row array; dp[c] += dp[c − 1] row by row, which adds "from above" (old dp[c]) and "from left" (new dp[c − 1]).
</>Solution (Java)
import java.util.*;
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1); // first row
for (int r = 1; r < m; r++)
for (int c = 1; c < n; c++)
dp[c] += dp[c - 1]; // from above + from left
return dp[n - 1];
}
}!Common mistake
Using int for the combinatorial formula C(m+n−2, m−1) without care — intermediate products overflow.
Complexity
- Time: O(m·n).
- Space: O(n).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon