Min Cost Climbing Stairs - The Discovery Journey

The Problem

LC 746: Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

---

Layer 1: Designer's Brain - What Problem Are We Actually Solving?

The Confusion Point

Common Mistake: Mixing Two Problems

You might confuse this with Climbing Stairs (LC 70): "How many ways can you reach step n?"

But this is Min Cost Climbing Stairs (LC 746): "What's the cheapest way to reach the top?"

Different problems, different DP states!

Problem 1: Climbing Stairs (LC 70)

• Question: "How many distinct ways to climb n stairs (1 or 2 steps at a time)?"
• State: dp[i] = number of ways to reach step i
• Transition: dp[i] = dp[i-1] + dp[i-2] (sum of ways)

Problem 2: Min Cost Climbing Stairs (LC 746) ← This is YOUR problem

• Question: "Each step has a cost. What's the minimum cost to reach the top?"
• State: dp[i] = minimum cost to reach position i
• Transition: dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

---

Layer 2: The Messy Discovery Journey

Discovery Step 1: What does the input look like?

cost = [10, 15, 20]
        ↑   ↑   ↑
     step0 step1 step2

Key Insights You Might Miss

1. You can start at step 0 OR step 1 (for free!)
2. You pay the cost when you LEAVE a step, not when you arrive
3. The "top" is beyond the last step (position n, where n = cost.length)

Discovery Step 2: What does dp[i] represent?

Designer's first attempt (WRONG):

"dp[i] = minimum cost to reach step i"

Why This Fails

When you reach step i, you haven't paid cost[i] yet!

The cost is paid when you LEAVE the step, not when you ARRIVE.

Designer's refined attempt (CORRECT):

"dp[i] = minimum cost to reach position i, having already paid all costs along the way"

This means when you're at position i, you've already paid for all the steps you took to get there.

Discovery Step 3: What's the recurrence relation?

Chronological thought process:

1. "To reach position i, where could I come from?"

   • From step (i-1): cost to reach (i-1), then pay cost[i-1] to jump
   • From step (i-2): cost to reach (i-2), then pay cost[i-2] to jump

2. "So dp[i] should be..."

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

The Recurrence Insight

To reach position i:

• Option A: Be at step (i-1), pay cost[i-1], jump 1 step → arrive at i
• Option B: Be at step (i-2), pay cost[i-2], jump 2 steps → arrive at i

Choose the cheaper option!

Discovery Step 4: What are the base cases?

Think physically:

• You can start at step 0 or step 1 for free
• So: dp[0] = 0 and dp[1] = 0

Why Zero?

You haven't paid anything yet—you're just standing there at your starting position, ready to jump.

You only pay when you LEAVE your starting position!

---

Layer 3: What Does "Top of the Floor" Mean?

Look at Example 1:

cost = [10, 15, 20]
indices: 0   1   2

Output is 15 - starting at index 1, pay 15, climb two steps.

Discovery Question

"Wait, if I climb two steps from index 1, I'm at index 3... but there's no index 3!"

The Insight: The "top" is position n (one past the last step). It's like:

cost =    [10, 15, 20, ???]
indices:   0   1   2   3 (TOP)

The top is a virtual position you reach AFTER leaving the staircase.

---

Layer 4: Coder's Brain - Building the Solution

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];  // +1 because top is beyond last step

    // BASE CASES: Start at step 0 or 1 for free
    dp[0] = 0;
    dp[1] = 0;

    // RECURRENCE: For each position, choose cheaper path
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(
            dp[i-1] + cost[i-1],  // pay cost[i-1] to jump from step (i-1)
            dp[i-2] + cost[i-2]   // pay cost[i-2] to jump from step (i-2)
        );
    }

    // Return cost to reach the top (beyond last step)
    return dp[n];
}

Data Structure Choices:

• Why array? We need to look back 2 steps, and we build sequentially
• Why n+1 size? We need dp[n] to represent the top
• Why not optimize to O(1) space yet? Clarity first - you can optimize to two variables later

---

Layer 5: Edge Cases as Concept Validators

Edge Case 1: cost = [10, 15, 20]

Trace:

dp[0] = 0  (start here free)
dp[1] = 0  (start here free)
dp[2] = min(dp[1] + cost[1], dp[0] + cost[0])
      = min(0 + 15, 0 + 10)
      = 10

Now reaching the TOP (position 3):

dp[3] = min(dp[2] + cost[2], dp[1] + cost[1])
      = min(10 + 20, 0 + 15)
      = 15 ✓

Path: Start at step 1 → jump to step 3 (top), pay cost[1] = 15

Validator Question

"Why isn't the answer 10 (starting at step 0)?"

Answer: Because from step 0, you'd pay 10 to jump to step 1 or 2. Then you'd need to pay MORE to reach the top. Starting at step 1 and jumping directly is cheaper!

Edge Case 2: cost = [1,100,1,1,1,100,1,1,100,1]

Critical steps:

dp[0] = 0
dp[1] = 0
dp[2] = min(0 + 100, 0 + 1) = 1     // from step 0, pay 1
dp[3] = min(1 + 1, 0 + 100) = 2     // from step 2, pay 1
dp[4] = min(2 + 1, 1 + 1) = 2       // from step 2, pay 1 (skip step 3!)

Key Insight

At dp[4], even though we could come from dp[3], it's cheaper to come from dp[2]:

• dp[3] + cost[3] = 2 + 1 = 3
• dp[2] + cost[2] = 1 + 1 = 2 ✓

The DP automatically finds: "Sometimes jumping from further back is cheaper than taking the nearest step."

Your Mental Model: "Should I always take the cheapest step?"

Reality: No! It's about the cumulative path, not local decisions. The DP solves this optimally.

---

Layer 6: What You Were Missing

Common Wrong Attempt:

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];

    dp[0] = cost[0];  // ❌ Paying cost too early
    dp[1] = cost[0];  // ❌ This doesn't make sense

    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i-1], dp[i-2]);  // ❌ Missing cost payment
    }

    return dp[n];
}

The Gaps in This Thinking

1. dp[0] = cost[0]: You're saying "it costs cost[0] to reach step 0"

   • Reality: It costs NOTHING to START at step 0
   • You only pay cost[0] when LEAVING step 0

2. dp[1] = cost[0]: You're saying "it costs cost[0] to reach step 1"

   • Reality: It costs NOTHING to START at step 1
   • If you reached step 1 FROM step 0, then yes, you'd have paid cost[0], but you can start at step 1 directly!

3. Missing cost in recurrence: You forgot to add the cost when jumping

   • Should be: dp[i-1] + cost[i-1], not just dp[i-1]

Better Attempt (Closer):

dp[0] = 0;  // ✓ Starting is free
dp[1] = 0;  // ✓ Starting is free

for (int i = 2; i <= n; i++) {
    dp[i] = Math.min(
        dp[i-1] + cost[i-1],  // ✓ CORRECT!
        dp[i-2] + cost[i-2]   // ✓ CORRECT!
    );
}

The Recurrence Was Right!

Your recurrence relation Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) was perfect from the start! 🎯

Only the base cases were wrong.

---

Layer 7: The Complete Correct Solution

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];  // +1 for the top position

    // Base cases: starting at step 0 or step 1 is free
    dp[0] = 0;
    dp[1] = 0;

    // Fill dp array: for each position, choose the cheaper path
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(
            dp[i-1] + cost[i-1],  // pay cost[i-1] to jump from step (i-1)
            dp[i-2] + cost[i-2]   // pay cost[i-2] to jump from step (i-2)
        );
    }

    // Return cost to reach the top (position n)
    return dp[n];
}

What Changed From Wrong Code:

Wrong	Correct	Why
dp[0] = cost[0]	dp[0] = 0	Starting is free
dp[1] = cost[0]	dp[1] = 0	Starting is free
i < n	i <= n	Need to calculate dp[n] (the top)
Missing cost addition	+ cost[i-1]	Pay to leave the step

---

Layer 8: The Meta-Pattern

Framework for DP Problems

1. Clarify the state transition:

   • "When do I pay the cost?" → When leaving, not entering
   • "What does dp[i] represent?" → Cost to reach position i

2. Draw a small example by hand:

   cost = [10, 15, 20]
           ↓   ↓   ↓
   steps:  0   1   2   TOP

3. Trace the physical action:

   • "I'm at step 1, I pay 15, I jump to the TOP"
   • This gives dp[3] = dp[1] + cost[1] = 0 + 15 = 15

4. Verify base cases match problem constraints:

   • "Can start at step 0 or 1" → dp[0] = 0, dp[1] = 0

---

The Core Insight

Critical Understanding: Timing of Cost Payment

Cost is paid when LEAVING a step, not when ARRIVING

Therefore, to reach position i, you pay the cost of the step you're leaving (i-1 or i-2), not the cost of position i itself.

This is the conceptual hurdle - once you see that dp[i] is cumulative cost to arrive at position i (not the cost of being at i), everything clicks.

Base Case Reasoning:

Starting positions are FREE (no cost to begin there). You only pay when you take your first step AWAY from your starting position.

---

Key Takeaways

1. ✅ State Definition: dp[i] = minimum cost to reach position i (having paid all costs along the way)

2. ✅ Cost Timing: Pay cost[i] when LEAVING step i, not when arriving at it

3. ✅ Base Cases: Starting is free → dp[0] = 0, dp[1] = 0

4. ✅ Top Position: The top is at position n (one beyond the last step)

5. ✅ Recurrence: Choose the cheaper of two paths:

   • Jump from (i-1): dp[i-1] + cost[i-1]
   • Jump from (i-2): dp[i-2] + cost[i-2]

Complexity: Time O(n), Space O(n) - can be optimized to O(1) space with two variables