🧩 Unique Paths II - Formal Proof

Why the recurrence relation still works with obstacles, and why setting obstacle cells to zero is mathematically sound

SERIES NAVIGATION

📘 Unique Paths Series:

1. The Discovery Journey - How humans naturally discover the solution
2. Plain English Proof - Accessible logical reasoning
3. Formal Proof - Mathematical rigor and certainty
4. 🧩 When Reality Gets Messy - Discovery | Plain Proof | Formal Proof (You are here)

THE PROBLEM (LC 63)

A robot is located at the top-left corner of an m × n grid. The robot can only move either down or right.

New Constraint: Some cells contain obstacles (marked as 1). The robot cannot step on obstacles.

What we're proving: The formula dp[i][j] = dp[i-1][j] + dp[i][j-1] still holds, with one modification: if cell (i,j) contains an obstacle, then dp[i][j] = 0.

---

🎯 What We're Proving

We want to show that for Unique Paths II, the formula works even when obstacles are present.

More formally: The counting logic doesn't break when we add the constraint that certain cells are forbidden.

THE THEOREM

For any cell (i,j) in the grid:

If cell (i,j) contains an obstacle then dp[i][j] = 0

Otherwise if both i > 0 and j > 0 then dp[i][j] = dp[i-1][j] + dp[i][j-1]

---

📐 Setting Up the Proof

Let me define our terms precisely so we're all on the same page.

Definition 1 (The Grid with Obstacles)

Let G be an m × n grid where some cells may contain obstacles.

A cell (i,j) is either:

• Free (passable), or
• Blocked (contains an obstacle)

---

Definition 2 (Valid Path)

A valid path from (0,0) to (i,j) is a sequence of cells where:

• Every cell in the sequence is free
• We start at (0,0)
• We end at (i,j)
• Each consecutive pair of cells represents either a right move or a down move

KEY DIFFERENCE FROM UNIQUE PATHS I

In Unique Paths I, every cell was automatically free.

Now we have to check whether a cell is passable before we can consider paths through it.

---

Definition 3 (dp function)

The function dp[i][j] represents the number of valid paths from (0,0) to (i,j).

---

📜 The Main Theorem

THEOREM

For any cell (i,j) in the grid, the number of valid paths dp[i][j] satisfies:

1. If cell (i,j) contains an obstacle then dp[i][j] = 0

2. Otherwise if both i > 0 and j > 0 then dp[i][j] = dp[i-1][j] + dp[i][j-1]

Let me prove this in two parts because we have two cases to handle.

---

Part One: Proving Obstacle Cells Have Zero Paths

CLAIM 1

If cell (i,j) contains an obstacle, then dp[i][j] = 0.

Proof of Claim 1:

This follows directly from the definition of a valid path.

Remember that a valid path is a sequence of cells where every cell in the sequence must be free.

If cell (i,j) contains an obstacle, then (i,j) is not a free cell.

Therefore, no valid path can include (i,j) as part of its sequence, which means no valid path can end at (i,j).

The set of valid paths to (i,j) is empty, so its cardinality is zero.

Therefore dp[i][j] = 0. ∎

THIS PART IS STRAIGHTFORWARD

You can't stand on an obstacle, so you can't reach it via any path.

The count is necessarily zero.

---

Part Two: Proving the Recurrence for Free Cells

Now comes the more interesting part. We need to prove that when (i,j) is a free cell, the recurrence relation from Unique Paths I still applies.

CLAIM 2

If cell (i,j) is free and both i > 0 and j > 0, then:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Proof of Claim 2:

Let S be the set of all valid paths from (0,0) to (i,j).

Since (i,j) is a free cell, S might be non-empty. We want to count the size of S.

I'm going to use the same partitioning strategy from the original proof, but I need to be more careful now because obstacles might affect which paths are valid.

---

Step 1: Partition S into two groups

Let me partition S into two groups:

• Let A = set of paths in S whose final move is DOWN

  • These paths arrive at (i,j) from cell (i-1,j)

• Let B = set of paths in S whose final move is RIGHT

  • These paths arrive at (i,j) from cell (i,j-1)

---

Step 2: Showing that A and B partition S

Part 2a: A and B together contain every path in S

Consider any valid path P in S. This path ends at (i,j), and since we know i and j are both positive, the path must have made at least one move to get there.

What was the final move of path P?

Since we can only move right or down, the final move was either:

• Down from (i-1,j) → then P belongs to A
• Right from (i,j-1) → then P belongs to B

Therefore every path in S belongs to either A or B.

---

Part 2b: A and B don't overlap

Suppose path P belongs to both A and B.

Then P's final move is simultaneously:

• Down from (i-1,j), AND
• Right from (i,j-1)

But a path has exactly one final move determined by its second-to-last position.

Since (i-1,j) ≠ (i,j-1), we have a contradiction.

Therefore A and B are disjoint. ∎

IDENTICAL TO ORIGINAL PROOF

So far this is identical to the original proof.

The presence of obstacles elsewhere in the grid doesn't change the fact that any path to (i,j) must arrive via one of two possible final moves.

---

Step 3: Counting the paths in A

Here's where we need to be careful about obstacles.

The set A contains all valid paths to (i,j) that pass through (i-1,j) as their second-to-last cell.

CRITICAL QUESTION

What if cell (i-1,j) contains an obstacle?

This is the critical question.

Case 1: If (i-1,j) is blocked

If (i-1,j) has an obstacle, then no valid path can pass through it.

Remember our Definition 2: A valid path requires every cell in the path to be free.

So if (i-1,j) has an obstacle, then the set A must be empty, meaning |A| = 0.

Case 2: If (i-1,j) is free

I can use the same bijection argument from the original proof.

Every path in A consists of:

1. A path from (0,0) to (i-1,j)
2. Followed by one down move

There's a one-to-one correspondence between paths in A and valid paths to (i-1,j).

Therefore |A| = dp[i-1][j].

---

COMBINING THE TWO CASES

If (i-1,j) has an obstacle then dp[i-1][j] = 0 (by Part One) and |A| = 0

If (i-1,j) is free then |A| = dp[i-1][j]

In both cases: |A| = dp[i-1][j]

---

Step 4: Counting the paths in B

By identical reasoning, the size of B equals dp[i,j-1].

• If cell (i,j-1) contains an obstacle, then dp[i,j-1] = 0 and B is empty
• If cell (i,j-1) is free, then there's a bijection between B and the set of valid paths to (i,j-1)

Either way: |B| = dp[i,j-1]

---

Step 5: Computing the total

Since A and B partition S and we know the size of each group, we can apply the addition principle.

The total number of paths in S equals:

|S| = |A| + |B|

Therefore:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

This completes the proof for free cells. ∎

---

💡 Why This Proof is Beautiful

Let me point out what makes this proof elegant.

THE ELEGANCE

We didn't need separate formulas for:

• "when there's an obstacle nearby" vs.
• "when there's no obstacle nearby"

The same formula works in all cases because the zero value for obstacle cells acts as a natural blocker in the arithmetic.

When you compute dp[i-1][j] + dp[i][j-1], you might be:

• Adding 0 + some number if one direction is blocked
• Adding some number + some number if both directions are clear
• Adding 0 + 0 if both directions are blocked

The formula adapts automatically without requiring conditional logic in the recurrence relation itself.

KEY INSIGHT

Setting dp for obstacle cells to zero isn't just a convenient convention.

It's a mathematical necessity that follows from the definition of valid paths, and it causes the recurrence relation to naturally handle all the different cases.

---

🔄 The Propagation Property

There's one more important property I want to prove, because it explains why obstacles can create "unreachable regions" without us explicitly checking for connectivity.

THEOREM (PROPAGATION OF IMPOSSIBILITY)

If there is no valid path from (0,0) to cell (i,j), then dp[i][j] = 0.

Proof:

We'll prove this by considering how unreachability can occur.

There are two ways a cell can be unreachable:

---

Case 1: The cell itself contains an obstacle

We already proved that dp[i][j] = 0 in this case (Part One).

---

Case 2: The cell is free but isolated from the start position

This means that every possible path from (0,0) that would reach (i,j) must pass through at least one obstacle at some point.

For case two, consider our recurrence relation. If (i,j) is free, then:

dp[i][j] = dp[i-1][j] + dp[i,j-1]

Now, if there's no valid path to (i,j), then there must be:

• No valid path from (i-1,j) to (i,j), AND
• No valid path from (i,j-1) to (i,j)

Analysis for (i-1,j):

The only way to reach (i,j) from (i-1,j) is to take one down move, and we know (i,j) is free.

So if (i-1,j) were reachable, then (i,j) would also be reachable.

Therefore (i-1,j) must be unreachable, which means dp[i-1][j] = 0.

Analysis for (i,j-1):

By the same logic, (i,j-1) must be unreachable, so dp[i,j-1] = 0.

Therefore:

dp[i][j] = 0 + 0 = 0

∎

AUTOMATIC PROPAGATION

This proof shows that unreachability propagates through the grid automatically via the recurrence relation.

If a cell can't be reached, its dp value will be zero, which will contribute zero to any cells that depend on it.

---

📊 Understanding Through an Example

Let me walk through a concrete example to show how the proof plays out with actual numbers.

Consider this small grid where X marks obstacles:

S  .  X
.  .  .
.  .  E

Let me prove that dp[0][2] = 0 and show how this affects later cells.

---

Cell (0,2) - The Obstacle

For cell (0,2), we would normally compute:

dp[0][2] = dp[-1][2] + dp[0][1]

But wait, there's an obstacle at (0,2).

By Part One of our proof, dp[0][2] = 0 immediately. We don't even need to look at the neighbors.

---

Cell (1,2) - Free but Blocked from Above

It's a free cell, so we use the recurrence relation:

dp[1][2] = dp[0][2] + dp[1][1]

We know dp[0][2] = 0 because of the obstacle.

Let's say we've already computed dp[1][1] = 2.

Then:

dp[1][2] = 0 + 2 = 2

WHAT HAPPENED

The obstacle blocked one of the two paths that would normally contribute to cell (1,2), but the other direction was still open, so we got a nonzero result.

The formula handled this automatically by adding zero from the blocked direction.

---

Cell (2,2) - The Destination

We compute:

dp[2][2] = dp[1][2] + dp[2][1]

Both of these neighboring cells are free and reachable.

Let's say dp[1][2] = 2 and dp[2][1] = 3.

Then:

dp[2][2] = 2 + 3 = 5

The obstacle at (0,2) reduced the number of paths to the destination, but didn't make it unreachable.

PROOF IN ACTION

Each step of this example follows directly from our proof:

• When we hit an obstacle, we set the value to zero
• When we hit a free cell, we add the values from above and left
• The zeros from obstacle cells propagate through the calculations, reducing path counts in cells that depend on them

---

🔄 Comparing to the Original Proof

Let me explicitly show what changed and what stayed the same between Unique Paths I and Unique Paths II.

┌─────────────────────────────────────────────────────┐
│  WHAT STAYED THE SAME                               │
└─────────────────────────────────────────────────────┘

✅ Partition paths based on final move
   → Still works because final move is still DOWN or RIGHT
   → Obstacles don't create new types of moves

✅ Bijection between groups and neighbor cells
   → Still exists, but one or both sets might be empty
   → Empty sets have size zero

✅ Addition principle to combine counts
   → Still works because adding zero doesn't break it
   → Empty sets contribute zero to the sum

┌─────────────────────────────────────────────────────┐
│  WHAT CHANGED                                       │
└─────────────────────────────────────────────────────┘

🔄 Added one new case: blocked cells
   → Simple case: dp[i][j] = 0 by definition
   → No fancy reasoning required

🔄 Bijection sets might be empty
   → If neighbor is blocked, corresponding group is empty
   → Empty group contributes zero to the sum

THE MATHEMATICAL STRUCTURE IS IDENTICAL

We just added one new case to handle, which is when a cell is blocked.

And that case is so simple that it doesn't require any fancy reasoning. A blocked cell has zero paths by definition.

---

💪 What Makes the Proof Work

The proof relies on several mathematical principles working together.

1. The Partition Principle

If you split a set into non-overlapping pieces, the total count is the sum of the piece counts.

This works regardless of whether some pieces are empty.

---

2. The Bijection Principle

If two sets can be perfectly matched up in a one-to-one way, they have the same size.

This works even when both sets are empty, because empty sets match perfectly and both have size zero.

---

3. Zero as the Additive Identity

Adding zero to a number gives you the same number back.

This is why the formula dp[i-1][j] + dp[i][j-1] works regardless of which neighbors are blocked.

The blocked neighbors contribute zero, which doesn't change the sum from the unblocked neighbors.

---

4. Problem Constraint

Every path must consist entirely of free cells.

This is what forces obstacle cells to have a dp value of zero, which then propagates through the recurrence relation.

---

🧪 Testing Your Understanding

VERIFY YOUR COMPREHENSION

Question 1: Why is Group A Empty?

In our proof, we showed that if (i-1,j) has an obstacle, then group A is empty.

Can you explain in your own words why no path can belong to group A in this situation?

Click for answer

Group A contains paths whose second-to-last cell is (i-1,j).

By the definition of a valid path, every cell in the path sequence must be free (no obstacles).

If (i-1,j) contains an obstacle, then it's not a free cell.

Therefore, no valid path can include (i-1,j) in its sequence.

Since every path in group A must pass through (i-1,j), and no valid path can do so, group A must be empty.

---

Question 2: Obstacle at Start Position

The proof showed that the formula works whether neighbors are blocked or free.

But what if the starting cell (0,0) has an obstacle? Does our proof handle this case correctly, and what would the final answer be?

Click for answer

Yes, the proof handles this correctly!

If (0,0) contains an obstacle, then by Part One of our proof, dp[0][0] = 0.

Since all other cells depend on paths from (0,0), and there are no paths starting from an obstacle, every cell in the grid will propagate this zero.

The final answer at the destination would be 0 (no valid paths).

This makes logical sense: if you can't even start the journey (start is blocked), you can't reach any destination.

---

Question 3: Passing Through Obstacles

Suppose we modify the problem so that you can move through obstacles but you cannot stop on them.

In other words, you can pass through an obstacle cell as long as your path doesn't end there.

Would our recurrence relation still hold? What would break in the proof?

Click for answer

No, the recurrence relation would NOT hold in its current form.

What breaks:

Our proof relies on Definition 2: A valid path must have every cell in the sequence be free.

If we allow passing through obstacles, this definition changes fundamentally.

The problem:

Now a path to (i,j) could pass through (i-1,j) even if (i-1,j) is an obstacle!

The bijection between group A and paths to (i-1,j) would break, because:

• Some paths in A passed through the obstacle at (i-1,j)
• But dp[i-1][j] would still be 0 (you can't stop there)
• So |A| ≠ dp[i-1][j]

What we'd need:

We'd need a completely different state definition, tracking not just position but also whether we're currently on an obstacle (and thus must keep moving).

---

Question 4: Unreachable Free Cell

In the propagation theorem, we proved that unreachable cells automatically get a dp value of zero.

Can you construct a grid where a free cell is unreachable because obstacles surround it, and verify that our recurrence relation gives it a value of zero?

Click for answer

Example grid (X = obstacle, F = free):

S  F  X
X  F  X
X  X  X

The free cell at (1,1) is surrounded by obstacles (except for cells that are also unreachable).

Let's trace the dp values:

Row 0: dp[0][0] = 1, dp[0][1] = 1, dp[0][2] = 0 (obstacle)
Row 1: dp[1][0] = 0 (obstacle), dp[1][1] = ?, dp[1][2] = 0 (obstacle)

For dp[1][1]:

dp[1][1] = dp[0][1] + dp[1][0]
         = 1 + 0
         = 1

Wait! This cell is reachable via (0,1) → (1,1).

Let me fix the example to truly surround it:

S  X  X
X  F  X
X  X  X

Now:

Row 0: dp[0][0] = 1, dp[0][1] = 0 (obstacle), dp[0][2] = 0 (obstacle)
Row 1: dp[1][0] = 0 (obstacle), dp[1][1] = ?, dp[1][2] = 0 (obstacle)

For dp[1][1]:

dp[1][1] = dp[0][1] + dp[1][0]
         = 0 + 0
         = 0

Verified! The unreachable free cell at (1,1) automatically gets dp = 0 because both its dependencies are zero (blocked or unreachable).

---

🎯 Key Takeaways

WHAT YOU SHOULD REMEMBER

1. The Recurrence Survives:

   • Same formula: dp[i][j] = dp[i-1][j] + dp[i][j-1]
   • Only add one guard: if obstacle then dp[i][j] = 0

2. Zero as Natural Blocker:

   • Obstacle cells have zero paths by definition
   • Zero propagates automatically through arithmetic
   • No special cases needed in the formula

3. Proof Structure Unchanged:

   • Partition by final move still works
   • Bijection still exists (might be to empty set)
   • Addition principle still applies

4. Propagation of Impossibility:

   • Unreachable cells automatically get zero
   • No explicit connectivity checking needed
   • The recurrence handles it naturally

5. Mathematical Elegance:

   • One simple modification (zero for obstacles)
   • Entire proof generalizes automatically
   • Beauty of well-chosen definitions

---

Remember: The most elegant mathematical proofs are those where a single insight (obstacles → zero paths) cascades through the entire structure, making everything work automatically.