🎯 Min Cost Climbing Stairs - The Discovery Journey
The Problem (Quick Glance)
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.
Initial Observations:
- Can start at step 0 or step 1 for free
- Once you pay a step's cost, you can climb 1 or 2 steps
- Need to reach "the top" (which is beyond the last step)
Let's start solving!
1. My First Approach: Thinking Recursively
My thought process:
"To reach position i, I need to choose between:
- Coming from position (i-1) and paying cost[i-1]
- Coming from position (i-2) and paying cost[i-2]
I'll pick whichever is cheaper!"
Solution 1: Unoptimized Recursive (Brute Force)
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
return minCost(n, cost); // We want to reach position n (top of floor)
}
private int minCost(int i, int[] cost) {
// Base cases: starting positions are free
if (i == 0) return 0;
if (i == 1) return 0;
// Recursive case: choose cheaper path
int fromPrevStep = minCost(i - 1, cost) + cost[i - 1];
int fromTwoStepsBack = minCost(i - 2, cost) + cost[i - 2];
return Math.min(fromPrevStep, fromTwoStepsBack);
}
Complexity Analysis:
- Time: O(2^n) - Exponential! 😱
- Space: O(n) - Recursion call stack depth
Why This Is Slow:
minCost(5)
├── minCost(4)
│ ├── minCost(3)
│ │ ├── minCost(2) ← Calculated here
│ │ │ ├── minCost(1)
│ │ │ └── minCost(0)
│ │ └── minCost(1)
│ └── minCost(2) ← Calculated AGAIN here!
│ ├── minCost(1)
│ └── minCost(0)
└── minCost(3) ← Calculated AGAIN here!
├── minCost(2) ← Calculated YET AGAIN!
└── minCost(1)
I'm recalculating the same subproblems over and over!
minCost(2) gets computed multiple times, minCost(3) gets computed multiple times, etc.
This is horribly inefficient! Time complexity: O(2^n)
My realization: "Wait, I'm doing the same work repeatedly. Can I remember what I've already computed?"
2. Optimization Round 1: Adding Memoization (Top-Down DP)
My thought: "Let me cache the results so I don't recalculate them!"
Solution 2: Top-Down DP with Memoization
class Solution {
int[] arr; // memoization array
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
arr = new int[n + 1];
// Initialize memoization array with -1
for (int i = 0; i <= n; i++) {
arr[i] = -1;
}
// Base cases
arr[0] = 0;
arr[1] = 0;
return func(n, cost);
}
int func(int i, int[] cost) {
// Base case: if we've already computed this
if (arr[i] != -1) {
return arr[i];
}
int fromPrevStep;
int fromTwoStepsBack;
if (arr[i - 1] != -1) {
fromPrevStep = arr[i - 1];
} else {
fromPrevStep = func(i - 1, cost);
}
fromPrevStep += cost[i - 1];
if (arr[i - 2] != -1) {
fromTwoStepsBack = arr[i - 2];
} else {
fromTwoStepsBack = func(i - 2, cost);
}
fromTwoStepsBack += cost[i - 2];
int min = Math.min(fromPrevStep, fromTwoStepsBack);
arr[i] = min;
return min;
}
}
📝 Alternative: Previous Implementation
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] memo = new int[n + 1];
Arrays.fill(memo, -1); // -1 means "not computed yet"
return minCost(n, cost, memo);
}
private int minCost(int i, int[] cost, int[] memo) {
// Base cases: starting positions are free
if (i == 0) return 0;
if (i == 1) return 0;
// Check if already computed
if (memo[i] != -1) return memo[i]; // Cache hit! 🎯
// Recursive case: choose cheaper path
int fromPrevStep = minCost(i - 1, cost, memo) + cost[i - 1];
int fromTwoStepsBack = minCost(i - 2, cost, memo) + cost[i - 2];
// Store result in cache before returning
memo[i] = Math.min(fromPrevStep, fromTwoStepsBack);
return memo[i];
}
Complexity Analysis:
- Time: O(n) - Each subproblem computed once! ✨
- Space: O(n) memo array + O(n) call stack = O(n) total
Why This Is Fast:
minCost(5, memo)
├── minCost(4, memo)
│ ├── minCost(3, memo)
│ │ ├── minCost(2, memo) ← Computed and cached
│ │ │ ├── minCost(1, memo) → 0
│ │ │ └── minCost(0, memo) → 0
│ │ └── minCost(1, memo) → 0
│ └── minCost(2, memo) ← Cache hit! Returns immediately 🚀
└── minCost(3, memo) ← Cache hit! Returns immediately 🚀
Each subproblem is computed exactly once and reused from cache.
Time complexity drops from O(2^n) to O(n)! 🎉
My next thought: "This is much better! But I'm still using recursion with a call stack. Can I eliminate that?"
3. Optimization Round 2: Going Iterative (Bottom-Up DP)
My thought: "Instead of recursing from top down, what if I build the solution from bottom up?"
Solution 3: Bottom-Up DP with Tabulation
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;
// BUILD TABLE: For each position, choose cheaper path
for (int i = 2; i <= n; i++) {
int fromPrevStep = dp[i - 1] + cost[i - 1];
int fromTwoStepsBack = dp[i - 2] + cost[i - 2];
dp[i] = Math.min(fromPrevStep, fromTwoStepsBack);
}
// Return cost to reach the top (beyond last step)
return dp[n];
}
Complexity Analysis:
- Time: O(n) - Single loop through all positions
- Space: O(n) - DP array only (no recursion stack!)
Why Bottom-Up?
- ✅ No recursion overhead - Simple loop instead of function calls
- ✅ No stack overflow risk - Works for very large n
- ✅ Better cache locality - Sequential memory access
- ✅ Easier to optimize further - Can reduce to O(1) space
Execution Trace for cost = [10, 15, 20]:
Initial: dp = [0, 0, ?, ?]
i=0 i=1 i=2 i=3
i=2: dp[2] = min(dp[1] + cost[1], dp[0] + cost[0])
= min(0 + 15, 0 + 10)
= 10
dp = [0, 0, 10, ?]
i=3: dp[3] = min(dp[2] + cost[2], dp[1] + cost[1])
= min(10 + 20, 0 + 15)
= 15
dp = [0, 0, 10, 15]
Return: dp[3] = 15 ✓
My observation: "Wait, I only ever need the last 2 values. Do I really need the entire array?"
4. Final Optimization: Space Optimization (O(1) Space)
My thought: "Since I only look back 2 positions, I can just track 2 variables!"
Solution 4: Space-Optimized Bottom-Up
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// Only track last 2 values
int prev2 = 0; // dp[i-2]
int prev1 = 0; // dp[i-1]
for (int i = 2; i <= n; i++) {
int fromPrevStep = prev1 + cost[i - 1];
int fromTwoStepsBack = prev2 + cost[i - 2];
int current = Math.min(fromPrevStep, fromTwoStepsBack);
// Slide the window forward
prev2 = prev1;
prev1 = current;
}
return prev1;
}
Complexity Analysis:
- Time: O(n) - Same as before
- Space: O(1) - Only 3 variables! 🎯
Execution Trace for cost = [10, 15, 20]:
Initial: prev2=0, prev1=0
i=2: current = min(prev1 + cost[1], prev2 + cost[0])
= min(0 + 15, 0 + 10) = 10
prev2=0, prev1=10
i=3: current = min(prev1 + cost[2], prev2 + cost[1])
= min(10 + 20, 0 + 15) = 15
prev2=10, prev1=15
Return: prev1 = 15 ✓
5. Solution Evolution Summary
| Approach | Time | Space | Recursion? | Key Insight |
|---|---|---|---|---|
| 1. Unoptimized Recursive | O(2^n) | O(n) stack | Yes | Establishes recurrence relation |
| 2. Top-Down (Memoization) | O(n) | O(n) + O(n) stack | Yes | Cache eliminates redundant work |
| 3. Bottom-Up (Tabulation) | O(n) | O(n) array | No | Build iteratively, no recursion |
| 4. Space-Optimized | O(n) | O(1) | No | Only need last 2 values |
The Learning Journey:
- 🤔 Start with natural recursive thinking
- 💡 Realize we're repeating work → add memoization
- ⚡ Eliminate recursion overhead → go bottom-up
- 🎯 Recognize we only need 2 values → space optimize
6. Deep Dive: Understanding Why This Works
Now that we've built the solution, let's understand the deeper concepts.
6.1 Common Confusion Points
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])
6.2 State Definition & Cost Timing
What does dp[i] represent?
Designer's first attempt (WRONG):
"dp[i] = minimum cost to reach step i"
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.
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.
"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.
6.3 The Recurrence Relation Explained
Chronological thought process:
-
"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
- From step (i-1): cost to reach (i-1), then pay
-
"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
)
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!
6.4 Base Cases Explained
Think physically:
- You can start at step 0 or step 1 for free
- So:
dp[0] = 0anddp[1] = 0
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!
7. Validation & Edge Cases
7.1 Edge Case Analysis
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
"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!)
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 = 3dp[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.
7.2 Common Mistakes & Corrections
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];
}
-
dp[0] = cost[0]: You're saying "it costscost[0]to reach step 0"- Reality: It costs NOTHING to START at step 0
- You only pay
cost[0]when LEAVING step 0
-
dp[1] = cost[0]: You're saying "it costscost[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!
-
Missing cost in recurrence: You forgot to add the cost when jumping
- Should be:
dp[i-1] + cost[i-1], not justdp[i-1]
- Should be:
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!
);
}
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.
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 |
8. Meta-Patterns & Key Takeaways
-
Start with recursive thinking:
- What are my choices at each step?
- What's the base case?
-
Identify repeated work:
- Am I solving the same subproblem multiple times?
-
Add memoization:
- Cache results to avoid redundant computation
-
Convert to iterative:
- Build solution bottom-up if possible
-
Optimize space:
- Do I really need to store all intermediate results?
The Core Insight
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
- ✅ Start with recursion: Natural way to think about the problem
- ✅ Optimize with memoization: Eliminate redundant computation (O(2^n) → O(n))
- ✅ Convert to bottom-up: Remove recursion overhead
- ✅ Space optimize: Only keep what you need (O(n) → O(1))
- ✅ State Definition:
dp[i]= minimum cost to reach position i (having paid all costs along the way) - ✅ Cost Timing: Pay
cost[i]when LEAVING step i, not when arriving at it - ✅ Base Cases: Starting is free →
dp[0] = 0,dp[1] = 0 - ✅ Top Position: The top is at position n (one beyond the last step)
The Learning Journey: Start simple, optimize iteratively, understand deeply.