Unique Paths II

Partition Equal Subset Sum

House Robber II

Count grid paths from the top-left to the bottom-right when some cells are blocked by obstacles.

You are given an `m x n` integer grid `obstacleGrid` where `0` marks an empty cell and `1` marks an obstacle. Starting from the top-left cell, return the number of distinct paths to the bottom-right cell, moving only **right** or **down** and never stepping onto an obstacle.

If the start or the destination cell is an obstacle, there are `0` valid paths.

**Input / output**
- Input: `obstacleGrid: int[][]`
- Output: `int` (number of obstacle-free paths)

**Examples**
1. `obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]` returns `2`; the single middle obstacle leaves two ways around it.
2. `obstacleGrid = [[0,1],[0,0]]` returns `1`.
3. `obstacleGrid = [[1]]` returns `0` because the start itself is blocked.

**Constraints**
- `1 <= m, n <= 100`
- `obstacleGrid[i][j]` is `0` or `1`
- The answer fits in a 32-bit signed integer.

**Follow-up**
The full grid of subresults is easy to write but uses `O(m*n)` memory. Can you compute the answer with only `O(n)` extra space by reusing a single row?

- Let `ways[r][c]` be the number of obstacle-free paths that reach cell `(r, c)`.
- You can only arrive from the cell above or the cell to the left, so `ways[r][c] = ways[r-1][c] + ways[r][c-1]`.
- An obstacle cell is unreachable, so its count is `0`.

Set up the grid recurrence

- Seed the start cell with `1` unless it is an obstacle.
- Sweep every cell in row-major order, zeroing obstacles and summing the reachable neighbors otherwise.
- The answer sits in the bottom-right cell.

Fill a full 2D table

- When you process row by row, `dp[c]` already holds the count from the row above, and `dp[c-1]` holds the freshly updated count from the left.
- So a single 1D array of width `cols` is enough: `dp[c] += dp[c-1]` for open cells, `dp[c] = 0` for obstacles.

Reuse a single rolling row

- Initialize `dp[0]` from the start cell, then sweep every row updating the same array in place.
- Obstacles reset their column to `0`; open cells add the value to their left. The final answer is `dp[cols-1]`.

Optimal O(n)-space sweep

Trace `[[0,0,0],[0,1,0],[0,0,0]]` with the rolling row.

| after row | dp |
|---|---|
| row 0 `[0,0,0]` | `[1,1,1]` |
| row 1 `[0,1,0]` | `[1,0,1]` |
| row 2 `[0,0,0]` | `[1,1,2]` |

The answer is `dp[2] = 2`.

Dry run

- Seeding the start cell as `1` even when it is an obstacle, which over-counts every path.
- Forgetting that an obstacle must reset its cell to `0` in the rolling array, not just skip it.
- Assuming a blocked destination still has paths.
- Follow-up: how would diagonal moves or a cost per cell change the recurrence?

Common mistakes and follow-ups

- A single free cell has exactly one path; a single blocked cell has none.
- A fully blocked row or column cuts every path to `0`.
- A blocked start or destination yields `0` regardless of the rest of the grid.

Edge cases to test mentally

A row-by-row sweep over one rolling DP row counts obstacle-free paths. Time is `O(m*n)` and extra space is `O(n)`.