Skip to main content

🎯 The Designer's Journey: From Problem to Recursion

The Designer's Mindset

Before writing any code, a great designer asks: "What decision am I making at each point?"

This document takes you through the messy thought process of discovering the recursive solution to Min Cost Climbing Stairs.

1. Discovery & Recursive Foundation​

1.1 Designer's Thought Process​

Step 1: What am I actually trying to compute?​

When you see this problem, the FIRST question isn't "how do I code this?" but rather:

"What decision am I making at each point?"

Let me simulate the messy thought process:

"Hmm, I'm at some step i. To reach the TOP from here, what are my choices?"

1. I can climb 1 step (pay cost[i]) and then solve "what's the min cost from i+1 to top?"
2. I can climb 2 steps (pay cost[i]) and then solve "what's the min cost from i+2 to top?"
💡 AHA MOMENT

The problem has optimal substructure!

The solution to "min cost from step i" depends on solutions to smaller subproblems (from i+1 and i+2).

Step 2: What's the recursive definition?​

Now the designer thinks:

"Let me define a function that captures this decision..."

minCost(i) = minimum cost to reach TOP starting from step i

The recursive relationship:

minCost(i) = cost[i] + min(minCost(i+1), minCost(i+2))
Read it as:

"If I'm at step i, I pay cost[i], then I choose the cheaper of the two paths ahead."

1.2 Base Cases & Starting Points​

Step 3: What are my base cases?​

"When do I stop recursing? When I've reached or passed the top!"

Initial thoughts:

  • If i >= n: I'm already at/past the top → cost = 0
  • If i == n-1: I'm at the last step → pay cost[n-1] and I'm done
  • If i == n-2: I'm at second-to-last → pay cost[n-2] and I'm done
Wait, can I simplify?

Yes! If i >= n, I'm already at the top, so return 0.

The recursion naturally handles the rest.

Final base case:

if (i >= n) return 0;

Step 4: How do I start?​

"The problem says I can start from step 0 OR step 1..."

So the answer is:

min(minCost(0), minCost(1))
The Intuition
  • Starting at 0: "What's the cheapest path from step 0 to top?"
  • Starting at 1: "What's the cheapest path from step 1 to top?"

Take the minimum of these two options!

1.3 Pure Recursive Implementation​

public int minCostClimbingStairs(int[] cost) {
    // We can start from step 0 or step 1
    return Math.min(
        minCost(cost, 0),
        minCost(cost, 1)
    );
}

// Returns: minimum cost to reach TOP starting from step i
private int minCost(int[] cost, int i) {
    int n = cost.length;

    // BASE CASE: Already at or past the top
    if (i >= n) {
        return 0;
    }

    // RECURSIVE CASE: Pay cost[i], then choose cheaper path
    int oneStep = minCost(cost, i + 1);
    int twoSteps = minCost(cost, i + 2);

    return cost[i] + Math.min(oneStep, twoSteps);
}
The Code Reads Like English
  1. "If I'm at or past the top" → return 0
  2. "Otherwise, pay my current cost" → cost[i]
  3. "Then choose the cheaper of the two paths ahead" → min(oneStep, twoSteps)

2. Understanding & Validation​

2.1 Recursion vs DP Connection​

Your DP Solution (Bottom-Up):​

dp[i] = Math.min(
    dp[i-1] + cost[i-1],  // came from i-1
    dp[i-2] + cost[i-2]   // came from i-2
)

The Recursive Solution (Top-Down):​

minCost(i) = cost[i] + Math.min(
    minCost(i+1),  // go to i+1
    minCost(i+2)   // go to i+2
)
🧠 Why Do They Look Different?

Your DP solution asks:

"To reach position i, where could I have come from?" (looking backward)

The recursive solution asks:

"Starting from position i, where can I go?" (looking forward)

They're solving the SAME problem, just from opposite directions!

2.2 Edge Cases & Concept Validation​

Test Case 1: Tiny Array​

cost = [10, 15]

Recursive trace:

min(minCost(0), minCost(1))

minCost(0) = 10 + min(minCost(1), minCost(2))
  ├─ minCost(1) = 15 + min(minCost(2), minCost(3))
  │    ├─ minCost(2) = 0 (base case)
  │    └─ minCost(3) = 0 (base case)
  │    → minCost(1) = 15 + 0 = 15
  └─ minCost(2) = 0
  → minCost(0) = 10 + min(15, 0) = 10

minCost(1) = 15

Answer: min(10, 15) = 10 ✓
Why does starting from 0 work?

Because we can skip step 1 entirely (2-step jump from 0 to top).

Test Case 2: All Same Costs​

cost = [1, 1, 1, 1]

Intuition: We should take 2-step jumps when possible.

Path 1:

Start at 0 → jump to 2 → jump to 4 (top)
Cost: 1 + 1 = 2

Path 2:

Start at 1 → jump to 3 → jump to 5 (top)
Cost: 1 + 1 = 2
Both work! ✓

The recursion naturally finds this without us explicitly coding the strategy.

2.3 Deepening Understanding​

The DP Problem-Solving Framework:​

  1. Identify the decision → "What choice am I making at each step?"
  2. Define the state → "What information do I need to track?"
  3. Write the recurrence → "How do smaller subproblems combine?"
  4. Find base cases → "When do I stop?"
  5. Code recursion → Pure recursive solution
  6. Add memoization → Cache overlapping subproblems (Top-Down DP)
  7. Convert to bottom-up → Iterative DP (what you wrote)
You jumped straight to step 7!

That works, but starting at step 5 (recursion) helps you understand WHY the DP works.

Questions to Deepen Understanding​

Q1: Why does i >= n return 0 instead of infinity?

Answer

Because reaching the top has no additional cost.

If we returned infinity, we'd be saying "it's impossible to reach the top from here," which is wrong.

Q2: Why can we start from BOTH 0 and 1?

Answer

The problem explicitly allows it. It's like having two entry points to a building.

Q3: How does memoization eliminate redundant work?

Answer

Draw the recursion tree for cost = [10, 15, 20]. You'll see minCost(2) gets called multiple times.

Memoization ensures we compute it only once.

Without memoization:

       minCost(0)
      /          \
  minCost(1)   minCost(2) ← computed
    /      \
minCost(2) minCost(3) ← computed AGAIN!

With memoization:

       minCost(0)
      /          \
  minCost(1)   minCost(2) ← computed & cached
    /      \
[cache hit] minCost(3) ← reuse cached value!

3. Evolution & Optimization​

3.1 Memoization Approach​

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    Integer[] memo = new Integer[n];  // null means "not computed yet"

    return Math.min(
        minCostMemo(cost, 0, memo),
        minCostMemo(cost, 1, memo)
    );
}

private int minCostMemo(int[] cost, int i, Integer[] memo) {
    int n = cost.length;

    if (i >= n) return 0;

    // Check cache
    if (memo[i] != null) return memo[i];

    // Compute and cache
    int result = cost[i] + Math.min(
        minCostMemo(cost, i + 1, memo),
        minCostMemo(cost, i + 2, memo)
    );

    memo[i] = result;
    return result;
}
How Memoization Works
  1. Before computing: Check if we already solved this subproblem
  2. If yes: Return the cached result
  3. If no: Compute, store in cache, then return

3.2 Complete Evolution Roadmap​

Your DP Journey (The Path for Every DP Problem)​

Problem Statement
       ↓
1. Recursive Definition (what you just learned)
       ↓
2. Add Memoization (Top-Down DP)
       ↓
3. Convert to Bottom-Up (Your original solution)
       ↓
4. Space Optimization (if possible)
Now you have the COMPLETE map! 🎯

Every DP problem follows this journey from recursive thinking to optimized iteration.

The Complete Evolution​

Evolution 1: Pure Recursion (Understanding)

// Time: O(2^n) - exponential!
// Space: O(n) - recursion stack
minCost(i) = cost[i] + min(minCost(i+1), minCost(i+2))

Evolution 2: Memoization (Top-Down DP)

// Time: O(n) - each state computed once
// Space: O(n) - memo array + recursion stack
if (memo[i] != null) return memo[i];
memo[i] = cost[i] + min(minCost(i+1, memo), minCost(i+2, memo));

Evolution 3: Bottom-Up DP (Your Solution)

// Time: O(n)
// Space: O(n) - dp array
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);

Evolution 4: Space Optimization

// Time: O(n)
// Space: O(1) - only track last 2 values
int prev2 = 0, prev1 = 0;
for (int i = 2; i <= n; i++) {
    int curr = min(prev1 + cost[i-1], prev2 + cost[i-2]);
    prev2 = prev1;
    prev1 = curr;
}

3.3 Key Takeaways & Next Steps​

Key Takeaways​

  1. ✅ Recursion is the foundation - It captures the problem structure naturally
  2. ✅ DP eliminates redundancy - Same subproblems → cache results
  3. ✅ Bottom-up is optimization - Iterative version of the recursive solution
  4. ✅ Think forwards OR backwards - Both directions solve the same problem
  5. ✅ Start simple, optimize later - Recursion → Memo → DP → Space optimization
The Designer's Secret

Great DP solutions start with clear recursive thinking.

Your bottom-up DP solution works because it's the iterative translation of the recursive pattern!

Next Steps to Deepen Your Mastery​

  1. Try memoization yourself - Add caching to the recursive solution
  2. Implement space optimization - Reduce O(n) space to O(1)
  3. Draw recursion trees - Visualize why memoization helps
  4. Solve similar problems - Fibonacci, House Robber, Decode Ways
The Journey Continues

You now understand why your DP solution works - it's the bottom-up version of the recursive pattern!

This thinking process applies to every DP problem you'll encounter. 🚀