Count the number of ways to travel from the top-left to bottom-right of a grid,
moving only right and down. With obstacles, this becomes a 2D DP where each
cell's value is the sum of the cell above and the cell to the left.
The Recurrence
C++ — unique paths with obstacles
int unique_paths(vector>& grid) {
int R = grid.size(), C = grid[0].size();
if (grid[0][0] == 1) return 0;
vector> dp(R, vector(C, 0));
dp[0][0] = 1;
// First row
for (int c = 1; c < C; c++)
dp[0][c] = grid[0][c] ? 0 : dp[0][c - 1];
// First column
for (int r = 1; r < R; r++)
dp[r][0] = grid[r][0] ? 0 : dp[r - 1][0];
// Fill rest
for (int r = 1; r < R; r++)
for (int c = 1; c < C; c++)
if (!grid[r][c])
dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
return dp[R - 1][C - 1];
}
Rust — unique paths
fn unique_paths(grid: &[Vec]) -> i64 {
let (r, c) = (grid.len(), grid[0].len());
if grid[0][0] == 1 { return 0; }
let mut dp = vec![vec![0i64; c]; r];
dp[0][0] = 1;
for j in 1..c { dp[0][j] = if grid[0][j] == 1 { 0 } else { dp[0][j-1] }; }
for i in 1..r { dp[i][0] = if grid[i][0] == 1 { 0 } else { dp[i-1][0] }; }
for i in 1..r {
for j in 1..c {
if grid[i][j] == 0 {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
dp[r-1][c-1]
}
💡 Space optimisation
Grid path DP only needs the previous row: dp[c] += dp[c-1].
Iterate left-to-right, and dp[c] naturally holds the value from
the row above (dp[r-1][c]) until you overwrite it with the
new sum. This gives O(C) memory instead of O(R×C).
Key Takeaways
→Grid paths: dp[r][c] = from above + from left.
→Handle first row/column as base cases. Obstacles set cell to 0.