π Unique Paths - Plain English Proof
Why
dp[i][j] = dp[i-1][j] + dp[i][j-1]must be true, using everyday reasoning
π Unique Paths Series:
- The Discovery Journey - How humans naturally discover the solution
- π Plain English Proof (You are here) - Accessible logical reasoning
- Formal Proof - Mathematical rigor and certainty
- When Reality Gets Messy - Adapting to obstacles
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.
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.
You either:
- Came from the cell directly above you, taking a step down β
- 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.
π¦ 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:
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?
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?
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β
β Every path belongs to exactly one group β No path got left out β No path appears in both groups
π’ 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:
- The journey from
(0,0)to(i-1,j) - 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.
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].
Let Me Make Sure This Makes Senseβ
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).
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)
π’ 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).
- We split all paths into two groups
- We counted the first group and got:
dp[i-1][j] - We counted the second group and got:
dp[i,j-1] - Since every path belongs to exactly one group, the total count is:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
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
πͺ 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.
𧱠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).
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.
π§ͺ Testing Your Understandingβ
Let me give you a way to check if this proof makes sense to you.
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.
π Key Takeawaysβ
-
The Formula is Inevitable:
- Not a lucky guess or pattern
- Follows from logical necessity
-
The Proof Structure:
- Partition paths by final move
- Count each partition separately
- Add the counts together
-
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
-
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
-
Everyday Logic:
- Uses principles we apply in daily life
- No advanced math required
- Just careful, systematic reasoning
π The Bridge to Other Proofsβ
This plain English proof sits between two other approaches:
Intuitive Discovery β Plain English Proof β Formal Mathematical Proof
-
- How you naturally discover the pattern
- Visual and experimental
-
Plain English Proof (You are here)
- Why the pattern must be true
- Accessible logical reasoning
-
- 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"
π¬ 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
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."