🧩 Unique Paths II - Plain English Proof

Why the formula still works with obstacles, explained using everyday reasoning

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 (You are here) | Formal Proof

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 works, with one simple rule: obstacle cells = 0.

---

🎯 What We're Actually Trying to Prove

We want to show two things:

1. If a cell has an obstacle on it, then the number of ways to reach that cell is zero
2. If a cell doesn't have an obstacle, then we can still use our addition formula from before

Think of it like this:

We had a formula that worked perfectly when the grid was empty.

Now someone threw some rocks onto the grid blocking certain squares.

We want to prove that our formula doesn't break—it just adapts to the new situation.

---

Part One: Why Obstacle Cells Must Have Zero Paths

Let me start with the easy part.

If there's an obstacle sitting on a cell, how many ways can you reach that cell?

The answer has to be zero, and here's why.

What Is a Path?

Remember what a path is. A path is like a trail you walk from the start to some destination.

Every step of your journey, you're standing on some cell in the grid. You walk from cell to cell until you reach your goal.

---

The Rock Problem

Now imagine cell (i,j) has a big rock on it.

Can your path end at that cell?

• ❌ No, because you can't stand on the rock

Can your path pass through that cell on the way to somewhere else?

• ❌ No, because you can't step on the rock even temporarily

THE LOGICAL CONCLUSION

Any path that would normally go through that cell is now impossible.

The cell is completely blocked off.

If you can't step on it and you can't end your journey there, then there are exactly zero ways to reach it.

This isn't something we're choosing or deciding—it's just a logical fact.

The number of paths to an obstacle cell must be zero.

---

Part Two: Why the Addition Formula Still Works for Free Cells

Now comes the more interesting part.

Let's say we're looking at a cell (i,j) that doesn't have an obstacle. It's just a regular empty square.

We want to prove: We can still calculate the number of paths by adding the numbers from the cell above and the cell to the left.

The Strategy

Here's how I'm going to prove it:

1. I'll use the exact same strategy from the original problem
2. Where we split all paths into two groups based on their last move
3. Then I'll carefully check whether obstacles mess up this strategy

---

Step 1: Every Path Takes a Final Step

Imagine you've just arrived at cell (i,j) after following some path from the start.

Think about your very last move. Where did you come from?

Well, you can only move right or down in this problem, so you must have arrived at (i,j) from one of two places:

1. You were at the cell directly above (i-1,j) and you moved down ↓
2. You were at the cell directly to the left (i,j-1) and you moved right →

NO THIRD OPTION

• ❌ You didn't jump there
• ❌ You didn't come from a diagonal
• ✅ Your last step was definitely one of these two moves

The Key Insight

I can take all the paths that reach (i,j) and sort them into two piles:

• Pile 1: All paths whose last move was DOWN
• Pile 2: All paths whose last move was RIGHT

Every single path goes into exactly one pile.

---

Step 2: Checking That We Didn't Miss Any Paths

Let me make sure we put every path somewhere.

Question: Is there any path to (i,j) that doesn't fit into either pile?

Think about it: Every path has to make a final move to get there. That final move is either down or right—there's no other possibility.

So every path definitely goes into one of the two piles. We didn't miss anything. ✅

---

Step 3: Checking That No Path Goes Into Both Piles

Now let me make sure we didn't put any path into both piles.

Question: Could a single path be in the down pile AND also in the right pile at the same time?

Answer: No, because a path has exactly one final move.

If I asked you "where were you standing right before you got to (i,j)?", you'd give me one answer:

• You were either at the cell above, OR
• The cell to the left

But you can't have been at both places at once.

CLEAN SEPARATION

Every path belongs to exactly one pile.

This is important because when we count, we don't want to accidentally count the same path twice.

---

Step 4: What If There's an Obstacle Above?

Here's where we need to think about obstacles.

Let's count how many paths are in the down pile (paths that arrived at (i,j) from the cell above).

THE CRITICAL QUESTION

What if the cell above has an obstacle on it?

If there's a rock sitting at position (i-1,j), can any path pass through there?

No, because we already proved that you can't step on obstacle cells.

---

So if the cell above has an obstacle, then the down pile must be completely empty. There are zero paths in that pile.

Not a single path can come from above because the cell above is blocked.

---

On the other hand, what if the cell above is free and clear?

Then every path in the down pile is really just a path that goes from the start to (i-1,j), with one extra down move added at the end.

This means: Number of paths in down pile = Number of paths to (i-1,j)

---

Let Me Make Sure This Makes Sense

If there are five different ways to reach the cell above, then by taking each of those five paths and adding one more down move, you get five different ways to reach (i,j) from above.

WHY THIS WORKS

You're not creating duplicates because:

• Those five paths to the cell above were all different

You're not missing any paths because:

• Every path that comes to (i,j) from above had to pass through the cell above first

---

The Clever Part

Whether the cell above is blocked or free, we can use the same counting formula:

• If it's blocked, then we already proved it has zero paths, so the down pile has zero paths
• If it's free, then the down pile has exactly as many paths as the cell above

THE UNIVERSAL TRUTH

Either way, the number of paths in the down pile equals whatever number we calculated for the cell above.

---

Step 5: The Same Logic Works for the Left Side

By the exact same reasoning, the number of paths in the right pile equals the number we calculated for the cell to the left.

• If that cell has an obstacle, its number is zero, so the right pile is empty
• If that cell is free, then there's a perfect match between paths in the pile and paths to that cell

---

Step 6: Adding Up the Total

Now we can count the total number of paths to (i,j):

1. We split all the paths into two piles
2. We counted the first pile and got: the number from the cell above
3. We counted the second pile and got: the number from the cell to the left
4. Since every path is in exactly one pile, the total count is just these two numbers added together

THE FORMULA STILL WORKS

Number of paths to (i,j) = Number from above + Number from left

This is exactly our addition formula from before.

---

💡 Why Zeros Don't Break the Formula

Let me point out something really cool about this proof.

Notice that we didn't need to change the formula when obstacles showed up.

We're still adding the number from above and the number from the left. The formula stays exactly the same.

What Changed?

What changed is that some of those numbers might now be zero:

• If the cell above has an obstacle → we're adding zero from that direction
• If the cell to the left has an obstacle → we're adding zero from that direction
• If both neighbors have obstacles → we're adding zero + zero = zero

THE FORMULA ADAPTS AUTOMATICALLY

The formula handles all these cases automatically.

We don't need to write something like:

"if there's an obstacle nearby, use a different formula"

The same formula works everywhere because zero has this special property where adding it doesn't change things.

---

The Money in Your Pockets Analogy

Think about it like this:

If I ask you to add up all the money in your pockets, and your left pocket is empty, you add:

• Zero from the left pocket
• Plus whatever is in the right pocket

You don't need a different method for adding money when one pocket is empty.

The same addition works—you just happen to be adding zero.

---

🔄 Why Unreachable Cells Automatically Get Zero

There's one more cool thing I want to show you.

Sometimes an obstacle doesn't just block one cell—it makes other cells unreachable too.

Like if you put a wall of obstacles cutting across the grid, you can't get to anything on the far side of that wall.

THE AUTOMATIC PROPAGATION

You might think we'd need to explicitly check whether a cell is cut off from the start.

But actually, our formula handles this automatically. Let me show you why.

---

The Isolated Cell Scenario

Imagine cell (i,j) is free and doesn't have an obstacle, but it's isolated from the start by a wall of obstacles somewhere earlier in the grid.

How many paths can reach it?

• Zero, because every path that would try to get there hits the obstacle wall first

---

What Our Formula Calculates

Now let's see what our formula calculates.

For cell (i,j), we add:

• The number from the cell above
• The number from the cell to the left

But think about it: If (i,j) is cut off from the start, then:

• The cell above is also cut off from the start → zero paths
• The cell to the left is also cut off from the start → zero paths

So we calculate: zero + zero = zero

AUTOMATIC DETECTION

The formula automatically figures out that the cell is unreachable, even though the cell itself doesn't have an obstacle!

The zero values from earlier cells propagate forward through the grid.

---

The Chain Reaction

It's like a chain reaction:

1. If a cell can't be reached → it gets marked as zero
2. Then any cell that depends on it → adds that zero into its calculation
3. The unreachability spreads automatically through the math

Obstacle at (0,1)
     ↓
dp[0][1] = 0
     ↓
dp[1][1] = dp[0][1] + dp[1][0]
         = 0 + something
         ↓
The zero propagates

---

🔄 Comparing to the Original Problem

Let me show you what stayed the same and what changed when we added obstacles.

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

✅ Core Idea:
   Split paths into groups based on the final move

✅ Counting Method:
   Count each group separately

✅ The Formula:
   Add the counts together

✅ Logical Structure:
   The proof is identical

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

🔄 Some Cells Have Zero Paths:
   Obstacle cells and unreachable cells = 0

🔄 This Affects Later Cells:
   Zeros propagate through the calculations

🔄 But Zero Works With Addition:
   Adding zero doesn't break anything

---

The Recipe Analogy

Think of it like a recipe:

Original problem = Following a recipe in a fully stocked kitchen

Obstacle problem = Following the same recipe when you're missing some ingredients

• Some of your measurements are zero (because you don't have that ingredient)
• But you still follow the same recipe steps
• You still add everything together at the end
• You're just adding some zeros into the mix

The recipe doesn't change—you just might be adding zero for certain ingredients.

---

🧪 Does This Make Sense?

Let me check if this proof feels solid to you.

SELF-TEST QUESTIONS

Question 1: Can you explain back to me in your own words why an obstacle cell must have zero paths?

Think about it, then click to check

An obstacle cell must have zero paths because:

1. A path is a sequence of cells you walk through
2. Every cell in the path must be free (you can stand on it)
3. If a cell has an obstacle, you can't stand on it
4. Therefore, no path can include that cell
5. So the number of paths ending at or passing through that cell = zero

It's a logical necessity, not a choice!

---

Question 2: Can you explain why the addition formula still works even when one of the neighboring cells has zero paths?

Think about it, then click to check

The addition formula still works because:

1. We're adding two numbers: paths from above + paths from left
2. If one neighbor is blocked, it contributes zero to the sum
3. Adding zero doesn't change the result: 0 + 5 = 5 and 5 + 0 = 5
4. The formula is universal: it works whether we're adding 3 + 2, 0 + 5, or 0 + 0
5. We don't need special cases—the math handles it automatically

Zero acts as a "nothing to add from this direction" signal, which is exactly what we want!

---

🎯 Key Takeaways

WHAT YOU SHOULD UNDERSTAND

1. Obstacle Cells = Zero Paths:

   • Can't step on them → Can't reach them
   • Logical necessity, not arbitrary choice

2. The Formula Doesn't Change:

   • Still: dp[i][j] = dp[i-1][j] + dp[i][j-1]
   • Just some numbers are now zero

3. Zero Doesn't Break Addition:

   • Adding zero leaves other numbers unchanged
   • Formula adapts automatically

4. Unreachability Propagates:

   • Zeros spread through the grid automatically
   • No need to explicitly check connectivity

5. Same Proof Structure:

   • Partition by final move
   • Count each partition
   • Add them together
   • Obstacles don't change the logic

---

🌉 The Bridge to Formal Proof

This plain English proof sits between intuition and formal mathematics:

PROOF PROGRESSION

Intuitive Discovery → Plain English Proof → Formal Mathematical Proof

1. When Reality Gets Messy

   • How obstacles break your initial solution
   • Discovering that zeros fix everything

2. Plain English Proof (You are here)

   • Why zeros must work
   • Accessible logical reasoning

3. Formal Proof

   • Rigorous mathematical proof
   • Partition principle and propagation theorem

Each level adds more rigor while keeping the same core truth:

• Discovery: "Setting obstacles to zero seems to work"
• Plain English: "Here's why it must work"
• Formal: "Here's the mathematical proof it works"

---

Remember: The best understanding comes from seeing the same truth from multiple angles. Discovery shows you the pattern, plain reasoning shows you why it's true, and formal proof shows you it's certain.