📘 Unique Paths - The Discovery Journey

How the human brain naturally discovers the DP solution

SERIES NAVIGATION

📘 Unique Paths Series:

1. 📘 The Discovery Journey (You are here) - 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 - Adapting to obstacles

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?

Example: 3×3 grid → 6 unique paths

Constraints: All cells are reachable (no obstacles)

---

🧠 The Designer's Brain: The Messy Discovery Process

First Thought: "What if I just try all paths?"

You're at the top-left corner of a 3×3 grid. You can only move right or down. Let's trace this out:

START (0,0)
├─ Go RIGHT to (0,1)
│  ├─ Go RIGHT to (0,2)
│  │  └─ Go DOWN to (1,2)
│  │     └─ Go DOWN to (2,2) ✓ END
│  │
│  └─ Go DOWN to (1,1)
│     ├─ Go RIGHT to (1,2)
│     │  └─ Go DOWN to (2,2) ✓ END
│     └─ Go DOWN to (2,1)
│        └─ Go RIGHT to (2,2) ✓ END
│
└─ Go DOWN to (1,0)
   ├─ Go RIGHT to (1,1)
   │  ├─ Go RIGHT to (1,2)
   │  │  └─ Go DOWN to (2,2) ✓ END
   │  └─ Go DOWN to (2,1)
   │     └─ Go RIGHT to (2,2) ✓ END
   │
   └─ Go DOWN to (2,0)
      └─ Go RIGHT to (2,1)
         └─ Go RIGHT to (2,2) ✓ END

THE PATTERN EMERGES

Every path is a sequence of decisions. For a 3×3 grid, you need:

• 2 moves RIGHT (R)
• 2 moves DOWN (D)
• Total: 4 moves

Wait... this is just asking: "In how many ways can I arrange 2 R's and 2 D's?"

RRDD
RDRD
RDDR
DRRD
DRDR
DDRR

That's 6 ways. Combinatorics: C(4,2) = 6.

---

🤔 But Wait... Let's Not Jump to Combinatorics Yet

The Recursive Insight (Usually the First Instinct)

Standing at any cell, I ask: "How many ways to reach the END from HERE?"

If I'm at cell (i,j):

• I can come from the cell ABOVE me (i-1, j)
• I can come from the cell to my LEFT (i, j-1)

CRITICAL INSIGHT #1

paths_to(i,j) = paths_to(i-1,j) + paths_to(i,j-1)

Why addition? Because these are mutually exclusive events:

• Paths coming from above are DIFFERENT from paths coming from left
• No path can simultaneously come from both directions

---

📊 Let's Trace This on a 3×3 Grid

I'll mark each cell with "how many ways to reach it from START (0,0)":

START
  ↓
  1  →  1  →  1
  ↓     ↓     ↓
  1  →  2  →  3
  ↓     ↓     ↓
  1  →  3  →  6
              ↑
             END

Why These Numbers?

STEP-BY-STEP REASONING

Top row: Only ONE way (keep going right)

1 → 1 → 1

Left column: Only ONE way (keep going down)

1
↓
1
↓
1

Cell (1,1): Can come from:

• (0,1) which has 1 way
• (1,0) which has 1 way
• Total: 1 + 1 = 2 ways

Cell (1,2): Can come from:

• (0,2) which has 1 way
• (1,1) which has 2 ways
• Total: 1 + 2 = 3 ways

Cell (2,1): Can come from:

• (1,1) which has 2 ways
• (2,0) which has 1 way
• Total: 2 + 1 = 3 ways

Cell (2,2) - THE END: Can come from:

• (1,2) which has 3 ways
• (2,1) which has 3 ways
• Total: 3 + 3 = 6 ways ✓

---

💡 The Critical Insight (Prerequisite You Might Be Missing)

Why Does paths_to(i,j) = paths_to(i-1,j) + paths_to(i,j-1) Work?

DEEP UNDERSTANDING REQUIRED

Property 1: Every path must make a FINAL MOVE

• You can't teleport to (i,j)
• Your last step was either DOWN (from i-1,j) or RIGHT (from i,j-1)

Property 2: Partition Principle

ALL paths to (i,j) can be split into two groups:

• Group A: Those whose final move was DOWN
• Group B: Those whose final move was RIGHT

These groups:

1. Don't overlap (can't simultaneously do both as final move)
2. Cover ALL possibilities (must come from somewhere)

Property 3: Bijection (One-to-One Mapping)

• Every path ending at (i-1,j) can be extended by one DOWN move to reach (i,j)
• Every path ending at (i,j-1) can be extended by one RIGHT move to reach (i,j)
• This creates a perfect correspondence

Therefore:

Total paths to (i,j) = |Group A| + |Group B|
                     = paths_to(i-1,j) + paths_to(i,j-1)

---

💻 The Coder's Brain: Why This Data Structure?

Now that we understand the logic, how do we store this?

Option 1: Recursion (Mirrors Our Thought Process)

function paths(i, j):
    if i == 0 or j == 0:
        return 1  // base case: edges
    return paths(i-1, j) + paths(i, j-1)

PROBLEM: REPEATED CALCULATIONS

We recalculate the same cells many times!

paths(2,2) calls paths(1,2) and paths(2,1)
paths(1,2) calls paths(0,2) and paths(1,1)
paths(2,1) calls paths(1,1) and paths(2,0)
                    ↑
           calculated TWICE!

This creates an exponential time complexity! 😱

---

Option 2: 2D Array (Memoization of Recursion)

We already calculated this grid:

1  1  1
1  2  3
1  3  6

WHY A 2D ARRAY?

Because our state has TWO dimensions (row, column).

Each unique (i,j) pair needs one storage slot.

The filling order matters:

• We need (i-1,j) and (i,j-1) BEFORE we can fill (i,j)
• So fill left-to-right, top-to-bottom (like reading a book)

int[][] dp = new int[m][n];

// Base case: first row and column
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

// Fill the grid
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}

return dp[m-1][n-1];

---

Option 3: 1D Array (Space Optimization)

KEY OBSERVATION

To fill row i, we only need row i-1.

Previous row: [1, 2, 3]
Current row:  [1, ?, ?]

To fill current[1]:

• Need previous[1] = 2 (from above)
• Need current[0] = 1 (from left)
• Result: 1 + 2 = 3

Even better: We can overwrite the array in-place!

Start:    [1, 1, 1]  // represents row 0

After updating position 1:
          [1, 2, 1]  // position 1 now represents row 1

After updating position 2:
          [1, 2, 3]  // completed row 1

Full Implementation:

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // first row: all 1s

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j-1];
            //      ↑       ↑
            //   from above  from left
        }
    }

    return dp[n-1];
}

SPACE COMPLEXITY

• 2D Array: O(m × n)
• 1D Array: O(n)
• Same time complexity: O(m × n)

---

🚨 Edge Cases as Concept Validators

Edge 1: 1×1 Grid

START = END

• Already at destination
• Answer: 1 way (do nothing)
• Tests: Base case handling

---

Edge 2: 1×n Grid (Single Row)

START → → → → END

• Only one path (keep going right)
• Answer: 1
• Tests: Do we handle the "only right moves" case?

---

Edge 3: m×1 Grid (Single Column)

START
  ↓
  ↓
  ↓
 END

• Only one path (keep going down)
• Answer: 1
• Tests: Do we handle the "only down moves" case?

---

Edge 4: Why Can't We Have 0 Paths?

FUNDAMENTAL CONSTRAINT

As long as m ≥ 1 and n ≥ 1, there's ALWAYS at least one path.

The grid's connectivity guarantees this.

Validates: Our understanding of the problem constraints.

---

🎯 The Meta-Process (Framework for ALL Problems)

SYSTEMATIC PROBLEM-SOLVING APPROACH

Step 1: Start with the simplest possible approach

"What if I just try everything?" → Recursion

Step 2: Find the pattern in the recursion

• Draw it out for small cases
• Look for repeated work

Step 3: Identify the state

• What information do I need to know? → (row, column)
• How many dimensions? → 2D problem → 2D array

Step 4: Find dependencies

• What do I need to calculate X? → Dependency graph
• This determines filling order

Step 5: Optimize storage

• Do I need ALL previous states? → Only previous row
• Can I reuse memory? → 1D array

---

📝 Visual Summary: The Three Approaches

┌─────────────────────────────────────────────────────┐
│  RECURSION (Intuitive but Slow)                     │
│                                                      │
│  paths(2,2)                                         │
│    ├─ paths(1,2)                                    │
│    │   ├─ paths(0,2) = 1                           │
│    │   └─ paths(1,1) ← REPEATED!                   │
│    │       ├─ paths(0,1) = 1                       │
│    │       └─ paths(1,0) = 1                       │
│    └─ paths(2,1)                                    │
│        ├─ paths(1,1) ← REPEATED!                   │
│        └─ paths(2,0) = 1                           │
│                                                      │
│  Time: O(2^(m+n)) - EXPONENTIAL! 😱                │
└─────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────┐
│  2D DP (Clear and Standard)                         │
│                                                      │
│     0   1   2                                       │
│   ┌───┬───┬───┐                                    │
│ 0 │ 1 │ 1 │ 1 │                                    │
│   ├───┼───┼───┤                                    │
│ 1 │ 1 │ 2 │ 3 │                                    │
│   ├───┼───┼───┤                                    │
│ 2 │ 1 │ 3 │ 6 │ ← Answer                           │
│   └───┴───┴───┘                                    │
│                                                      │
│  Time: O(m×n)  Space: O(m×n)                       │
└─────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────┐
│  1D DP (Space Optimized)                            │
│                                                      │
│  Initial:  [1, 1, 1]                               │
│  After i=1: [1, 2, 3]                              │
│  After i=2: [1, 3, 6] ← Answer at dp[2]            │
│                                                      │
│  Time: O(m×n)  Space: O(n)                         │
└─────────────────────────────────────────────────────┘

---

🧪 Test Your Understanding

VERIFY YOUR COMPREHENSION

Question 1: In a 4×4 grid, how many ways to reach cell (2,2)?

Hint: Build the grid up to that point:

1  1  1  1
1  2  3  4
1  3  ?  ?

Click for answer

Cell (2,2) = dp[1][2] + dp[2][1]
           = 3 + 3
           = 6 ways

Full grid:

1  1  1  1
1  2  3  4
1  3  6  10

---

Question 2: Why can't we fill the grid in reverse (bottom-right to top-left)?

Hint: Think about dependencies.

Click for answer

Each cell (i,j) depends on (i-1,j) and (i,j-1) (cells above and to the left).

If we start from bottom-right, we'd need values that haven't been calculated yet!

Exception: We COULD do reverse if we reversed the dependencies (using cells below and right), which is what Dungeon Game does.

---

Question 3: What if the robot could ALSO move diagonally? How does our formula change?

Hint: How many ways can you now enter cell (i,j)?

Click for answer

dp[i][j] = dp[i-1][j]     // from top
         + dp[i][j-1]     // from left
         + dp[i-1][j-1];  // from diagonal

Now each cell has 3 incoming paths instead of 2!

For a 3×3 grid with diagonal moves:

1  1  1
1  3  5
1  5  13

The center cell (1,1) now has 3 ways instead of 2!

---

🎓 Key Takeaways

WHAT YOU SHOULD REMEMBER

1. The Recursive Insight:

   • paths(i,j) = paths(i-1,j) + paths(i,j-1)
   • This is the foundation of the entire solution

2. Why Addition Works:

   • Mutually exclusive events (can't come from both directions simultaneously)
   • Exhaustive (covers all possibilities)

3. Three Implementation Levels:

   • Recursion → Simple but slow
   • 2D DP → Clear and standard
   • 1D DP → Space optimized

4. The Pattern Recognition:

   • When you see "count paths in grid"
   • Think: "build each cell from its dependencies"

5. Dependency Order Matters:

   • Must fill in topological order
   • Usually: left-to-right, top-to-bottom

---

🚀 Next Steps

After mastering Unique Paths, try these variations:

1. Unique Paths II - Add obstacles
2. Minimum Path Sum - Change from counting to optimization
3. Dungeon Game - Reverse the direction!
4. Triangle - Irregular grid structure

Each builds on the same core insight but adds one new complexity.

---

Remember: The best problem solvers don't just memorize solutions. They understand the discovery process that leads to the solution. This mental model will serve you for hundreds of similar problems.