Card 1 / 6
A robot starts at top-left of an m×n grid and can only move right or down. Count the unique paths to reach bottom-right.
State: dp[i][j] = paths to reach cell (i,j)
Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]
Space optimization: only need the previous row!
m |
n |
result |
|---|---|---|
3 |
2 |
3 |
3 |
3 |
6 |
3 |
7 |
28 |
1 |
5 |
1 |
First row and first column are all 1s (only one way to reach any cell there). Then fill row by row.
// A robot starts at top-left of an m x n grid and can only move right or down.
// Return the number of unique paths to reach the bottom-right corner.
int uniquePaths(int m, int n) {
std::vector<int> dp(n, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}Card 2 / 6
Same as Unique Paths, but some cells are blocked (marked 1). You cannot step on obstacles.
Key change: If a cell is an obstacle, dp[j] = 0 (no paths through it).
Watch edge cases: if start or end is blocked, return 0 immediately.