Skip to main content

πŸ“˜ Unique Paths - Plain English Proof

Why dp[i][j] = dp[i-1][j] + dp[i][j-1] must be true, using everyday reasoning

SERIES NAVIGATION

πŸ“˜ Unique Paths Series:

  1. The Discovery Journey - How humans naturally discover the solution
  2. πŸ”΄ Unoptimized Recursive - Pure recursion and exponential complexity
  3. πŸ“˜ Plain English Proof (You are here) - Accessible logical reasoning
  4. Formal Proof - Mathematical rigor and certainty
  5. When Reality Gets Messy - Adapting to obstacles

Section 1: Discovery & Problem Understanding​

1.1: Problem Analysis & Initial Thinking​

THE PROBLEM (LC 62)

A robot is located at the top-left corner of an m Γ— n grid. The robot can only move either down or right at any point in time.

Goal: How many possible unique paths are there to reach the bottom-right corner?

What we're proving: The formula dp[i][j] = dp[i-1][j] + dp[i][j-1] isn't just a patternβ€”it's a logical certainty.

🎯 What Are We Actually Trying to Prove?​

We want to show that the number of paths to any cell equals the number of paths to the cell above it, plus the number of paths to the cell to its left.

This isn't just a pattern we noticedβ€”it's something we can prove must always be true.

THINK OF IT LIKE THIS

I'm claiming that if you count carefully in two different ways, you'll always get the same answer.

The proof shows why those two counting methods must agree.

πŸ’‘ The Core Idea: Every Path Has a Last Step​

Here's the key insight that makes everything work.

Imagine you're standing at cell (i,j), having just arrived there. How did you get here?

Well, you must have taken a final step from somewhere. And because you can only move right or down, there are exactly two possibilities for where your final step came from.

THE ONLY TWO OPTIONS

You either:

  1. Came from the cell directly above you, taking a step down ↓
  2. Came from the cell directly to your left, taking a step right β†’

There's no third option:

  • ❌ You didn't teleport
  • ❌ You didn't come from a diagonal
  • βœ… Your final step was one of these two moves

This observation is going to be the foundation of our entire proof.

1.2: Thought Process & Strategy​

πŸ“¦ The Proof Strategy: Organizing Paths Into Groups​

Let me set up the proof carefully.

We have some cell at position (i,j), and we want to count all the possible paths that reach it from the starting position at (0,0).

Let's call this collection of paths our "total set of paths".

The Clever Part

I'm going to take all these paths and sort them into two groups based on what their final move was:

THE TWO GROUPS

Group 1: "Came from above"

  • All paths whose final move was DOWN ↓
  • These paths must have arrived at (i,j) from the cell above: (i-1,j)

Group 2: "Came from the left"

  • All paths whose final move was RIGHT β†’
  • These paths must have arrived at (i,j) from the cell to the left: (i,j-1)

Let me be really clear about what I just did:

I took every single path to (i,j) and put it into one of two boxes:

  • The "came from above" box
  • The "came from the left" box

βœ… Why These Two Groups Cover Everything​

First, let's make sure I actually put every path somewhere.

Question: Did I miss any paths? Could there be a path that doesn't fit into either group?

ANSWER: NO, EVERY PATH IS COVERED

Why? Because every path must end with some move.

Since you can only move down or right, every path's final move is either:

  • Down β†’ the path is in Group 1
  • Right β†’ the path is in Group 2

There's nowhere else for it to go. Every path has been accounted for.

🚫 Why No Path Appears in Both Groups​

Now let's make sure I didn't put any path in both boxes.

Question: Could a single path be in both the "came from above" group AND the "came from the left" group at the same time?

ANSWER: NO, IMPOSSIBLE

Why? Because a path has exactly one second-to-last step.

Think about it: If I asked you "where were you right before you got to (i,j)?" you can only give me one answer.

You were either at:

  • (i-1,j) (the cell above), OR
  • (i,j-1) (the cell to the left)

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

Your path took you through one specific sequence of cells, and the cell you were at right before the end is uniquely determined.

Summary So Far

CLEAN PARTITION ACHIEVED

βœ… Every path belongs to exactly one group βœ… No path got left out βœ… No path appears in both groups

1.3: Prerequisites & Core Insights​

πŸ’ͺ Why This Proof is Solid​

Let me point out what makes this proof actually work.

We relied on three fundamental ideas:

1. The Addition Principle

You can split a collection into non-overlapping groups and then count each group separately.

The total count is the sum of the group counts.

This is such a basic principle that we use it in everyday life without thinking:

Example: If you have 10 apples in one basket and 7 in another, you have 17 apples total.

We just applied this idea to paths instead of apples.

2. One-to-One Correspondence (Bijection)

There's a perfect correspondence between paths in the "came from above" group and paths to (i-1,j).

For every path to (i-1,j):

  • You can create exactly one path in our group by adding a down move

For every path in our group:

  • You can trace it backward to get exactly one path to (i-1,j)

This one-to-one matching guarantees the counts are equal.

3. Problem Constraints

You can only move right or down.

This constraint is what made it possible to partition the paths cleanly.

If the robot could move in other directions, our two groups wouldn't cover everything.

Section 2: Implementation & Deep Understanding​

2.1: Solution Implementation​

πŸ”’ Counting the First Group​

Now let's count how many paths are in the "came from above" group.

These are paths that end with a down move from (i-1,j) to (i,j).

The Key Insight

Every path in this group is made of two parts:

  1. The journey from (0,0) to (i-1,j)
  2. One final down move from (i-1,j) to (i,j)

That final move is the same for every path in this groupβ€”they all share it.

THE COUNTING TRICK

Counting paths in the "came from above" group is the same as counting paths from (0,0) to (i-1,j).

Why?

Because once you're at (i-1,j), there's only one way to finish: move down once.

Every unique way to reach (i-1,j) gives you a unique way to reach (i,j) via the down move.

This means: The number of paths in the "came from above" group equals dp[i-1][j].

πŸ”’ Counting the Second Group​

By the exact same reasoning, the "came from the left" group has a size equal to dp[i,j-1].

These paths are all the ways to reach (i,j-1), with one right move tacked on at the end.

  • Every unique path to (i,j-1) becomes a unique path to (i,j) when you add a right move
  • Every path that ends at (i,j) with a right move must have passed through (i,j-1)

🎯 Putting It All Together​

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

THE FINAL COUNT
  1. We split all paths into two groups
  2. We counted the first group and got: dp[i-1][j]
  3. We counted the second group and got: dp[i,j-1]
  4. Since every path belongs to exactly one group, the total count is:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
THIS IS NOT JUST A FORMULA

This must work because of the logical structure we just walked through:

  • The two groups cover all paths
  • They don't overlap
  • We know exactly how big each group is

2.2: Key Concepts & Mechanics​

Why the Counting Trick Works​

If there are, say, five different paths to get to (i-1,j), then by adding one final down move to each of them, you get five different paths to (i,j).

WHY THIS WORKS

You haven't created any duplicates because:

  • The paths to (i-1,j) were all different
  • You're adding the same final move to each one

You haven't missed any paths in this group because:

  • If a path ends with a down move to (i,j)
  • It must have passed through (i-1,j)

The Bijection Explained​

The one-to-one correspondence (bijection) is the mathematical foundation that makes our counting accurate:

  • Forward mapping: Each path to (i-1,j) β†’ add down move β†’ unique path to (i,j) in our group
  • Backward mapping: Each path in our group β†’ remove final down move β†’ unique path to (i-1,j)

This perfect matching guarantees:

  • No paths are counted twice
  • No paths are missed
  • The counts must be equal

Understanding the Recurrence​

The recurrence relation dp[i][j] = dp[i-1][j] + dp[i][j-1] emerges naturally because:

  1. Partition completeness: Every path ends with either down or right (no other options)
  2. Partition exclusivity: No path ends with both moves simultaneously
  3. Bijection property: Group sizes exactly match the subproblem counts
  4. Addition principle: Non-overlapping groups sum to the total

2.3: Edge Cases & Validation​

🧱 The Edge Cases Make Sense Too​

You might wonder: What about cells on the top row or left column?

For those cells, one of the terms in our formula would involve a cell that doesn't exist (like trying to access the cell above the top row).

HOW WE HANDLE EDGES

The way we handle this is to define those edge values directly:

First row (i=0): Exactly one path to any cell (just keep moving right)

dp[0][j] = 1 for all j

First column (j=0): Exactly one path to any cell (just keep moving down)

dp[i][0] = 1 for all i

These are our starting points.

Once we have those starting values, the recurrence relation takes over for all the interior cells.

And the proof we just walked through applies to any cell that has both a cell above it and a cell to its left.

Why Edge Cases Don't Break the Logic​

The edge cases are logically consistent with our proof:

  • Top row cells: Can only be reached from the left (one direction) β†’ 1 path
  • Left column cells: Can only be reached from above (one direction) β†’ 1 path
  • Interior cells: Can be reached from two directions β†’ sum of both paths

The recurrence relation naturally handles this by having one term evaluate to 0 (or be undefined) for edge cells, while the base case provides the correct value.

Section 3: Mastery & Visualization​

3.1: Practical Examples/Visualization​

πŸ§ͺ Testing Your Understanding​

Let me give you a way to check if this proof makes sense to you.

THOUGHT EXPERIMENT

Question: Imagine the robot could suddenly move in three directions: right, down, or diagonally down-right.

Would our proof still work?

Click to see the answer

Answer: Yes, with a modification!

Think about what would happen to our two groups. We'd need a third group now:

  • The "came from diagonal" group, containing paths whose final move was diagonal

The total would be:

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

The same proof structure would work, but with three groups instead of two.

This tells you that the proof wasn't some magical trick specific to this problem. It's a logical framework that adapts to the rules of the problem.

The structure of the proofβ€”split into groups based on the final move, count each group, add them upβ€”would work for any grid movement problem where you can categorize the final moves.

Visualizing the Partition​

Think of the proof visually:

  1. Start: All paths to (i,j) in one big pile
  2. Partition: Sort them into two boxes based on final move direction
  3. Count Box 1: Paths from above = dp[i-1][j]
  4. Count Box 2: Paths from left = dp[i,j-1]
  5. Sum: Total paths = Box 1 + Box 2

This visual model helps you understand why the formula must be correct.

3.2: Framework & Pattern Recognition​

πŸ”„ The Bridge to Other Proofs​

This plain English proof sits between two other approaches:

PROOF PROGRESSION

Intuitive Discovery β†’ Plain English Proof β†’ Formal Mathematical Proof

  1. The Discovery Journey

    • How you naturally discover the pattern
    • Visual and experimental

  2. Plain English Proof (You are here)

    • Why the pattern must be true
    • Accessible logical reasoning

  3. Formal Proof

    • Rigorous mathematical proof
    • Set theory and bijections

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

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

When to Use the Partition-by-Final-Move Strategy​

This proof technique is powerful and generalizable. Use it when:

  1. Discrete final states: You can categorize outcomes by their final step
  2. Known move options: The last move comes from a finite, known set of possibilities
  3. Subproblem decomposition: Removing the final step leaves a smaller, similar problem
  4. Path counting: You need to count sequences of choices

Examples where this applies:

  • Grid path counting (like this problem)
  • Combinatorial game theory
  • State machine analysis
  • Recursive sequence generation

3.3: Key Takeaways & Summary​

πŸŽ“ Key Takeaways​

WHAT YOU SHOULD UNDERSTAND

  1. The Formula is Inevitable:

    • Not a lucky guess or pattern
    • Follows from logical necessity

  2. The Proof Structure:

    • Partition paths by final move
    • Count each partition separately
    • Add the counts together

  3. Why It Works:

    • Every path has exactly one final move
    • We can categorize paths by this final move
    • The categories are non-overlapping and complete

  4. The Generalization:

    • This proof technique works for any grid problem
    • Just partition by the possible final moves
    • The number of groups equals the number of move directions

  5. Everyday Logic:

    • Uses principles we apply in daily life
    • No advanced math required
    • Just careful, systematic reasoning

πŸ’¬ Does This Feel Clearer Now?​

After reading this proof, you should be able to:

βœ… Explain why the formula must be true (not just that it works) βœ… See the logical necessity behind the recurrence relation βœ… Understand how to adapt this reasoning to similar problems βœ… Recognize when a problem can use this partition-by-final-move strategy

THE ULTIMATE TEST

Can you explain this proof to a friend who doesn't know dynamic programming?

If yes, you truly understand it! πŸŽ‰

Remember: Understanding why something is true is more powerful than memorizing that it is true. This proof gives you the "why."