233. Unique Paths with Obstacles

Why this mechanism works

Use the same predecessor recurrence as unique paths, but a blocked cell contributes no paths regardless of its neighbors. In a one-row table, dp[c] still holds the old row's count from above, while dp[c-1] already holds the current row's count from the left. Clearing an obstacle must happen before combining anything.

State and boundaries

Before updating column c, dp[c] is the top predecessor count; after updating, it is the current cell count. The left entry is already current-row state.

Protocol

1. Handle empty input.
2. Seed dp[0]=1 and other columns zero.
3. Scan rows left to right.
4. Set dp[c]=0 at an obstacle.
5. Otherwise add dp[c-1] when c>0.
6. Return the last column count.

Visualization

0 0 0
0 1 0   center count is forced to zero
0 0 0   two boundary routes survive

Python implementation

def paths_with_obstacles(grid):
    if not grid or not grid[0]:
        return 0
    dp = [0] * len(grid[0])
    dp[0] = 1
    for row in grid:
        for c, blocked in enumerate(row):
            if blocked:
                dp[c] = 0
            elif c:
                dp[c] += dp[c - 1]
    return dp[-1]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 paths_with_obstacles: if not grid or not grid[0]:
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]

L4 paths_with_obstacles: dp = [0] * len(grid[0])
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[0, 0, 0]

L5 paths_with_obstacles: dp[0] = 1
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 0, 0]

L6 paths_with_obstacles: for row in grid:
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 0, 0]; row=[0, 0, 0]

L7 paths_with_obstacles: for c, blocked in enumerate(row):
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 0, 0]; row=[0, 0, 0]; c=0; blocked=0

L7 paths_with_obstacles: for c, blocked in enumerate(row):
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 0, 0]; row=[0, 0, 0]; c=1; blocked=0

L11 paths_with_obstacles: dp[c] += dp[c - 1]
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 1, 0]; row=[0, 0, 0]; c=1; blocked=0

L7 paths_with_obstacles: for c, blocked in enumerate(row):
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 1, 0]; row=[0, 0, 0]; c=2; blocked=0

... 8 intermediate state changes omitted ...

L7 paths_with_obstacles: for c, blocked in enumerate(row):
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 0, 1]; row=[0, 0, 0]; c=1; blocked=0

L11 paths_with_obstacles: dp[c] += dp[c - 1]
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 1, 1]; row=[0, 0, 0]; c=1; blocked=0

L7 paths_with_obstacles: for c, blocked in enumerate(row):
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 1, 1]; row=[0, 0, 0]; c=2; blocked=0

L11 paths_with_obstacles: dp[c] += dp[c - 1]
grid=[[0, 0, 0], [0, 1, 0], [0, 0, 0]]; dp=[1, 1, 2]; row=[0, 0, 0]; c=2; blocked=0

L2 paths_with_obstacles: if not grid or not grid[0]:
grid=[[1]]

L4 paths_with_obstacles: dp = [0] * len(grid[0])
grid=[[1]]; dp=[0]

L5 paths_with_obstacles: dp[0] = 1
grid=[[1]]; dp=[1]

L6 paths_with_obstacles: for row in grid:
grid=[[1]]; dp=[1]; row=[1]

L7 paths_with_obstacles: for c, blocked in enumerate(row):
grid=[[1]]; dp=[1]; row=[1]; c=0; blocked=1

L9 paths_with_obstacles: dp[c] = 0
grid=[[1]]; dp=[0]; row=[1]; c=0; blocked=1

Why the solution is correct

The seed represents one path entering the open origin and is erased if that origin is blocked. At each open cell, old-top plus new-left counts all legal arrivals. At a blocked cell, zero correctly prevents every route from continuing through it. Row-major updates preserve these meanings.

Time and space

O(R*C) additions and O(C) integer storage; exact counts may exceed machine-word size.

Common mistakes

Skipping an obstacle without clearing dp[c] leaves stale paths from above. Updating right to left would read the wrong version of the left predecessor.

Reasoning card

Transfer exercise

Allow at most one obstacle removal by adding a second state for whether that removal has already been used.