Unique Paths II

Like Unique Paths, but some cells are blocked by obstacles (1 = blocked, 0 = free). Return the number of unique paths from top-left to bottom-right.

Function signature

func UniquePathsWithObstacles(obstacleGrid [][]int) int

Inputs / outputs

• obstacleGrid: grid of 0/1 values.
• Return: number of unique paths.

Example

0 0 0
0 1 0
0 0 0
Output: 2

Constraints

• 1 <= m, n <= 100

Core idea (near-solution)

DP with obstacles: if a cell is blocked, its path count is 0; otherwise sum from top and left.

Invariant: dp[c] is the path count for the current row at column c.

Algorithm (step-by-step)

1. If start is blocked, return 0.
2. Initialize dp[0] = 1.
3. For each cell (row-major):
   • If obstacle, set dp[c] = 0.
   • Else if c > 0, dp[c] += dp[c-1].
4. Return dp[n-1].

Correctness sketch

• Invariant: dp[c] is the path count for the current row at column c.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
0 0 0
0 1 0
0 0 0
Output: 2

Walk:
- row0: [1,1,1]
- row1 (obstacle at col1): [1,0,1]
- row2: [1,1,2] -> 2 paths

Pitfalls to avoid

• Forgetting to zero dp at obstacles.
• Mishandling the first row/column with obstacles.

Complexity

• Time: O(m*n).
• Extra space: O(n).

Implementation notes (Go)

• Update dp in-place; it represents the current row.