📘 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. 🔴 Unoptimized Recursive - Pure recursion and exponential complexity
3. Plain English Proof - Accessible logical reasoning
4. Formal Proof - Mathematical rigor and certainty
5. 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)

---

1. Discovery & Problem Understanding

1.1 Problem Analysis & 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 combinatorics approach works, but let's discover the DP insight that will serve us for hundreds of similar problems.

---

1.2 Recursive Insight & Pattern Recognition

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 ✓

---

1.3 Critical Prerequisites & Why It Works

The Critical Insight (Prerequisite You Might Be Missing)

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)

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

The formula works because:

1. Exhaustiveness: Every path to (i,j) must come from either (i-1,j) or (i,j-1) - there are no other possibilities
2. Mutual Exclusivity: A path cannot simultaneously arrive from both directions - the final move is unique
3. Independence: The number of ways to reach the two predecessor cells are independent events

This is the fundamental counting principle applied to path problems!

---

2. Implementation & Optimization

2.1 Recursive Solution (Intuitive but Slow)

Option 1: Pure 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! 😱

Visual: The Recursion Problem

┌─────────────────────────────────────────────────────┐
│  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! 😱                │
└─────────────────────────────────────────────────────┘

---

2.2 2D DP Array (Memoization)

The Coder's Brain: Why This Data Structure?

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

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)

Implementation: 2D DP Array

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];

Visual: 2D DP

┌─────────────────────────────────────────────────────┐
│  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)                       │
└─────────────────────────────────────────────────────┘

---

2.3 1D Array (Space Optimization)

Key Observation

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!

How In-Place Updating Works

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: 1D Array

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 COMPARISON

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

Visual: 1D DP

┌─────────────────────────────────────────────────────┐
│  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)                         │
└─────────────────────────────────────────────────────┘

---

3. Mastery & Validation

3.1 Edge Cases as Concept Validators

Edge Case 1: 1×1 Grid

START = END

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

---

Edge Case 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 Case 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 Case 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.

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!

---

3.2 Meta-Process & Framework

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

The Pattern Recognition

WHEN YOU SEE THIS PATTERN

Trigger: "count paths in grid"

Think: "build each cell from its dependencies"

Template:

// Base cases: edges = 1
// Recurrence: dp[i][j] = sum of predecessor cells
// Fill order: topological (usually left→right, top→bottom)

Dependency Order Matters

The order in which we fill the grid is critical:

Must fill in topological order:
  - Dependencies must be calculated BEFORE dependents
  - Usually: left-to-right, top-to-bottom
  - Sometimes reversed (Dungeon Game)

---

3.3 Key Takeaways & Summary

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 (O(2^(m+n)))
   • 2D DP → Clear and standard (O(m×n) time, O(m×n) space)
   • 1D DP → Space optimized (O(m×n) time, O(n) space)

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

Visual Summary: The Three Approaches

EVOLUTION PATH:

Recursion (Understanding)
    ↓
  [Identify repeated work]
    ↓
2D DP (Standard Solution)
    ↓
  [Optimize space usage]
    ↓
1D DP (Optimal Solution)

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.

THE FOUNDATION IS COMPLETE

You now understand the discovery process that leads to the solution.

This mental model will serve you for hundreds of similar problems - master the recursion first, optimize second! 🚀

---

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.