Skip to main content

Unique Paths: The Designer's Journey from Confusion to Clarity

LeetCode 62 - Understanding DP through path counting logic

The Problem​

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:​

Input: m = 3, n = 7 Output: 28

Example 2:​

Input: m = 3, n = 2 Output: 3

Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

  1. Right → Down → Down
  2. Down → Down → Right
  3. Down → Right → Down

The Designer's Journey: From Confusion to Clarity​

Stage 1: The Raw Problem (Designer's First Encounter)​

When I first see this problem, my brain goes:

  • "Count paths? That sounds like... a lot of paths"
  • "Can I just enumerate them? No, that's exponential explosion"
  • "Wait, there's structure here. I can only go RIGHT or DOWN"

The Key Realization (The "Aha" Moment)​

"To reach any cell, I must have come from either the cell above or the cell to the left"

This is THE prerequisite insight. Stop here if this doesn't click.

Why does this matter? Because it means:

  • The problem has optimal substructure: The number of ways to reach cell (i,j) depends ONLY on smaller subproblems
  • We're counting, not optimizing: We ADD possibilities, not choose between them

Stage 2: The Thought Process Unfolds​

Let me trace through the messy discovery journey:

Discovery Step 1: Start with the obvious​

"Let me try a tiny grid first. What about 2x2?"

Start → R
↓       ↓
D   →  End

Paths:

  1. Right then Down (R→D)
  2. Down then Right (D→R)

Answer: 2 paths

Discovery Step 2: Pattern recognition attempt​

"What about 2x3?"

Start → R → R
↓       ↓   ↓
D   →   R → End

Let me manually count:

  1. R→R→D
  2. R→D→R
  3. D→R→R

Answer: 3 paths

"Hmm, it went from 2 to 3. Not doubling. What's the pattern?"

Discovery Step 3: The breakthrough​

"Wait, let me think about the END cell instead of the START"

To reach the bottom-right corner, I must have arrived from either:

  • The cell directly above it, OR
  • The cell directly to the left of it

So: paths_to_end = paths_to_cell_above + paths_to_cell_left

THE DP FORMULA DISCOVERY

This simple observation is the entire solution!

Stage 3: Why Does This Lead to DP? (The Prerequisites)​

Prerequisite #1: Overlapping Subproblems​

"Do I need to calculate paths to cell (1,1) multiple times?"

To reach (2,2):
  - Need paths to (1,2)
  - Need paths to (2,1)

To reach (1,2):
  - Need paths to (0,2)
  - Need paths to (1,1)  ← LOOK HERE

To reach (2,1):
  - Need paths to (2,0)
  - Need paths to (1,1)  ← SAME CELL!

Yes! We'd recalculate (1,1) multiple times in a naive recursive solution.

Prerequisite #2: No Cycles​

"Can I get stuck in a loop?"

No! Because:

  • I can only move RIGHT (increasing column)
  • I can only move DOWN (increasing row)
  • I can never return to a previous cell

This means we can build solutions from smaller grids to larger grids.

Prerequisite #3: The Base Cases Are Obvious​

  • First row: Can only move RIGHT → only 1 way to reach each cell
  • First column: Can only move DOWN → only 1 way to reach each cell
1  1  1  1  1
1  ?  ?  ?  ?
1  ?  ?  ?  ?

Stage 4: Constructing the DP Formula (Coder's Brain Activates)​

The Mental Model​

"I'm filling a table. Each cell contains: number of ways to reach this cell from start"

The Formula Emerges Naturally​

dp[i][j] = number of ways to reach cell (i,j)

How do I reach (i,j)?

  • Come from above: (i-1, j)
  • Come from left: (i, j-1)
dp[i][j] = dp[i-1][j] + dp[i][j-1]

Why Addition, Not Max?​

Because we're counting all possibilities, not finding the best path.

  • In "minimum path sum" → we'd use min()
  • In "maximum path sum" → we'd use max()
  • In "count paths" → we use +

Stage 5: Edge Cases as Understanding Validators​

Edge Case 1: Single Row (m=1)​

Start → → → → End

Only 1 path (keep going right). Formula works because:

dp[0][j] = dp[-1][j] + dp[0][j-1]
dp[-1][j] doesn't exist (0 ways)
dp[0][j-1] = 1
Result: dp[0][j] = 1 ✓

Edge Case 2: Single Column (n=1)​

Start
↓
↓
↓
End

Only 1 path (keep going down). Formula works because:

dp[i][0] = dp[i-1][0] + dp[i][-1]
dp[i][-1] doesn't exist (0 ways)
dp[i-1][0] = 1
Result: dp[i][0] = 1 ✓

Edge Case 3: The Start Cell (0,0)​

"How many ways to reach the start from the start?"

Exactly 1 way: be there

This is our initialization: dp[0][0] = 1

Stage 6: The Code (Finally!)​

Now that we understand the WHY, the code writes itself:

class Solution {
    public int uniquePaths(int m, int n) {
        // Create table: dp[i][j] = ways to reach (i,j)
        int[][] dp = new int[m][n];

        // Base case: first row - only 1 way (keep going right)
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // Base case: first column - only 1 way (keep going down)
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        // Fill the table using our formula
        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];
    }
}

Stage 7: The Meta-Process (Framework for ALL DP Problems)​

Step 1: Look for Structure​

  • Can the problem be broken into smaller versions of itself?
  • Are there only a few ways to reach each state?

Step 2: Find the Recurrence​

  • "To compute X, what smaller things do I need?"
  • Work backwards from the goal

Step 3: Identify Base Cases​

  • What's trivially true?
  • What can I answer without computation?

Step 4: Check for Overlaps​

  • Will I recompute the same thing multiple times?
  • If yes → DP is appropriate

Step 5: Decide Bottom-Up vs Top-Down​

  • Bottom-up (tabulation): Build from base cases
  • Top-down (memoization): Compute recursively, cache results

The Deep Question: Why Does This Work?​

The fundamental insight is that path counting has additive structure:

Paths through A + Paths through B = Total paths (when A and B are disjoint)

Every path to (i,j) goes through EITHER (i-1,j) OR (i,j-1), never both.

So we can safely add them.

This is why the formula is addition, not max/min.

Critical Analysis: "Choices Depend on Future" Paradox​

The Confusion: What Does "Choices Depend on Future" Mean?​

When we said "choices depend on future outcomes → DYNAMIC PROGRAMMING", that was a heuristic for optimization problems (min/max path). But this problem is counting, not optimizing.

Let me separate these:

Two Types of DP Problems​

Type 1: Optimization (Min/Max)​

Example: Minimum path sum

  • "Should I go right or down?"
  • My choice NOW depends on which leads to a better FUTURE outcome
  • I need to know future costs to decide now

Type 2: Counting (This Problem)​

Example: Count unique paths

  • "How many ways exist?"
  • I'm not making choices at all! I'm aggregating possibilities
  • There's no decision to optimize

So Why Is This Problem DP At All?​

Let me rebuild the logic from scratch:

The Real DP Identifier: Overlapping Subproblems + Optimal Substructure​

Forget "choices depend on future" for counting problems.

Here's what's actually happening:

The Recursive Truth (What's Really Going On)​

Naive Recursive Thinking:

"How many ways to reach (2,3) from (0,0)?"

I could:

  1. Go RIGHT first → then count ways from (0,1) to (2,3)
  2. Go DOWN first → then count ways from (1,0) to (2,3)

Total = ways_from(0,1) + ways_from(1,0)

But wait, let's trace this:

paths(2, 3):
  = paths_from(0,1 → 2,3) + paths_from(1,0 → 2,3)

paths_from(0,1 → 2,3):
  = paths_from(0,2 → 2,3) + paths_from(1,1 → 2,3)

paths_from(1,0 → 2,3):
  = paths_from(1,1 → 2,3) + paths_from(2,0 → 2,3)
                ↑
            REPEATED!

We're calculating paths_from(1,1 → 2,3) multiple times!

The Correct DP Criterion for THIS Problem​

It's NOT about "choices affecting future"

It's about: "The answer to a question depends on answers to smaller questions, and those smaller questions repeat"

Let me reframe:

Question Decomposition:

Q: How many paths from (0,0) to (m-1, n-1)?

This question DECOMPOSES into:

  • How many paths from (0,0) to (m-2, n-1)? [then go DOWN]
  • How many paths from (0,0) to (m-1, n-2)? [then go RIGHT]

And THOSE questions decompose further...

The Overlapping Part:

To answer "paths to (2,2)", I need:

  • paths to (1,2)
  • paths to (2,1)

To answer "paths to (1,2)", I need:

  • paths to (0,2)
  • paths to (1,1) ← HERE

To answer "paths to (2,1)", I need:

  • paths to (1,1) ← AGAIN!
  • paths to (2,0)

The Revised Mental Model​

For Counting Problems:​

The structure is:

  1. Decomposition: Big problem = combination of smaller problems
  2. Overlap: Smaller problems appear multiple times
  3. Aggregation: Combine results (usually addition for counting)

There are NO "choices" here because:

  • We're not deciding which path to take
  • We're counting ALL possible paths
  • Every path is equally valid

When Does "Choices Depend on Future" Apply?​

It applies when you have CONSTRAINTS or OPTIMIZATION:

Example: Minimum Path Sum

"Should I go RIGHT (cost 5) or DOWN (cost 3)?"

This DEPENDS on:

  • What's the minimum cost from the right cell to the end?
  • What's the minimum cost from the down cell to the end?

I need FUTURE information to make the optimal CHOICE NOW.

Example: Unique Paths (this problem)

"How many paths total?"

I'm not choosing anything!

I'm counting:

  • ALL paths that go right first
  • PLUS all paths that go down first

No choice, no optimization, just counting.

The Corrected Framework​

DP Applies When:​

  1. The problem decomposes into subproblems (recursive structure)
  2. Subproblems overlap (same question asked multiple times)
  3. You can combine subproblem answers to get the main answer

The "Choices Depend on Future" Is A Subset:​

Optimization problems: You make choices based on future outcomes

  • "Should I take this item?" (0/1 Knapsack)
  • "Should I cut here?" (Rod Cutting)
  • "Should I buy/sell now?" (Stock Trading)

Counting problems: You aggregate all possibilities

  • "How many ways?" (This problem)
  • "How many subsequences?" (Count subsequences)
  • "How many trees?" (Unique BSTs)

The Deep Answer​

"Choices depend on future" doesn't apply here because:​

There are no choices. We're not deciding between paths—we're counting them all.

What DOES apply here:​

"The answer depends on answers to smaller versions of the same question, and those smaller versions repeat."

Better Heuristic for DP Detection​

Instead of "choices depend on future", use:

Ask yourself:

  1. Can I break this into smaller versions of the same problem? (Recursive structure)

    • Yes: "paths to (i,j)" breaks into "paths to (i-1,j)" and "paths to (i,j-1)"

  2. Will I ask the same question multiple times? (Overlapping subproblems)

    • Yes: "paths to (1,1)" is needed by both (2,1) and (1,2)

  3. Can I combine smaller answers to get the bigger answer? (Optimal substructure)

    • Yes: ADD the two smaller answers

If YES to all three → DP is appropriate

Conclusion​

The key insight is that counting problems use DP for aggregation, not decision-making.

This problem teaches us that DP isn't just about optimization—it's about efficiently computing answers by:

  1. Breaking problems into overlapping subproblems
  2. Storing results to avoid recomputation
  3. Combining results in a meaningful way (addition for counting, min/max for optimization)