206. Min Cost Climbing Stairs
🔗 LeetCode Problem: 746. Min Cost Climbing Stairs
📊 Difficulty: Easy
🏷️ Topics: Dynamic Programming, Array, 1D DP
Problem Statement
You are given an integer array cost where cost[i] is the cost of i-th 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 two steps to reach index 8.
- Pay 1 and climb two steps to reach the top.
The total cost is 6.
Constraints:
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
🌳 Visual Understanding - The Cost Staircase Problem
The Problem We're Solving:
Given: A staircase where each step has a COST
Goal: Find MINIMUM cost to reach the TOP
Rules:
- Can start from step 0 OR step 1 (both are ground level)
- After paying cost at step i, can climb 1 or 2 steps
- TOP is BEYOND the last step (not ON the last step)
Example: cost = [10, 15, 20]
TOP (Goal!) 🎯
↑
│
Step 2 (cost=20) ─────┤
│
Step 1 (cost=15) ─────┤
│
Step 0 (cost=10) ─────┤
│
Ground ───────────────┘
Can start from step 0 OR step 1
Need to reach TOP (beyond step 2)
Understanding "TOP" vs "Last Step":
CRITICAL: TOP ≠ Last Step!
cost = [10, 15, 20]
↑ ↑ ↑
0 1 2 (indices)
TOP is at position 3 (beyond array)!
Visual:
Index: 0 1 2 TOP
┌────┬────┬────┐ ↑
Cost: │10 │15 │20 │ │
└────┴────┴────┘ │
└─ Position 3 (goal)
To reach TOP, we can:
- Be at step 1, pay 15, jump 2 steps → TOP ✓
- Be at step 2, pay 20, jump 1 step → TOP ✓
All Possible Paths for Example 1:
cost = [10, 15, 20]
Path 1: Start at 0 → 1 → TOP
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start: Step 0
Pay: 10 (at step 0)
Jump: +1 step → reach step 1
Pay: 15 (at step 1)
Jump: +2 steps → reach TOP
Total: 10 + 15 = 25
Path 2: Start at 0 → 2 → TOP
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start: Step 0
Pay: 10 (at step 0)
Jump: +2 steps → reach step 2
Pay: 20 (at step 2)
Jump: +1 step → reach TOP
Total: 10 + 20 = 30
Path 3: Start at 1 → TOP
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start: Step 1
Pay: 15 (at step 1)
Jump: +2 steps → reach TOP
Total: 15 ✓ MINIMUM!
Path 4: Start at 1 → 2 → TOP
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start: Step 1
Pay: 15 (at step 1)
Jump: +1 step → reach step 2
Pay: 20 (at step 2)
Jump: +1 step → reach TOP
Total: 15 + 20 = 35
Minimum: 15 (Path 3) ✓
Visual for Example 2:
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Index: 0 1 2 3 4 5 6 7 8 9 TOP
Optimal Path (cost = 6):
━━━━━━━━━━━━━━━━━━━━━━━━━━━
Start at 0
Pay 1 at step 0, jump +2 → step 2
Pay 1 at step 2, jump +2 → step 4
Pay 1 at step 4, jump +2 → step 6
Pay 1 at step 6, jump +2 → step 8
Pay 1 at step 8, jump +2 → TOP
Path: 0 → 2 → 4 → 6 → 8 → TOP
Cost: 1 + 1 + 1 + 1 + 1 + 1 = 6 ✓
Notice: We SKIP all the expensive steps (100)!
This is why we need MINIMUM, not just any path! 🎯
🧠 The AHA Moment - Why Dynamic Programming?
Key Observation:
Standing at the TOP, how did we get here?
Step (n-1) Step (n-2)
│ │
│ +1 step │ +2 steps
└────────→ TOP ←────────┘
To reach TOP, we MUST have come from:
- Step (n-1) after paying cost[n-1], OR
- Step (n-2) after paying cost[n-2]
We want MINIMUM cost, so:
minCost(TOP) = min(
minCost(n-1) + cost[n-1],
minCost(n-2) + cost[n-2]
)
This is the DP recurrence! 🔑
Difference from Problem 205 (Climbing Stairs):
Problem 205: COUNT ways
ways(n) = ways(n-1) + ways(n-2)
Add both possibilities (SUM)
Problem 206: MINIMIZE cost
minCost(n) = min(
minCost(n-1) + cost[n-1],
minCost(n-2) + cost[n-2]
)
Choose better option (MIN)
PATTERN EVOLUTION:
Counting → SUM
Optimization → MIN/MAX
Same structure, different operation! 🎯
Why Not Greedy?
Greedy approach: "Always choose step with minimum cost"
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Greedy at step 0:
Option 1: Jump to step 1 (cost=100) ❌ expensive!
Option 2: Jump to step 2 (cost=1) ✓ cheap!
Choose: step 2
But what if choosing step 1 leads to better overall path?
Greedy makes LOCAL optimal choice
DP finds GLOBAL optimal solution
Example where greedy fails:
cost = [0, 2, 2, 1]
Greedy: 0 → 2 → 3 → TOP (cost: 0+2+1 = 3)
Optimal: 0 → 1 → 3 → TOP (cost: 0+2+1 = 3)
Both same in this case, but greedy can fail!
cost = [0, 1, 2, 3, 2]
Greedy: 0 → 1 → 3 → TOP (cost: 0+1+3 = 4)
Optimal: 0 → 2 → 4 → TOP (cost: 0+2+2 = 4)
Need to explore ALL paths to find true minimum! 🎯
Greedy won't work - need DP!
Why Dynamic Programming?
1. OVERLAPPING SUBPROBLEMS:
To find minCost(5), we need minCost(4) and minCost(3)
To find minCost(4), we need minCost(3) and minCost(2)
Notice: minCost(3) needed TWICE! ⚠️
2. OPTIMAL SUBSTRUCTURE:
Optimal solution contains optimal solutions to subproblems
minCost(TOP) = min of (optimal path via n-1, optimal path via n-2)
These TWO properties = Perfect for DP! 🎯
🔴 Approach 1: Brute Force (Recursion)
💡 Intuition
At each step i, we have 2 choices:
1. Jump 1 step → pay cost[i], then solve for (i+1)
2. Jump 2 steps → pay cost[i], then solve for (i+2)
Minimum cost from step i = cost[i] + min of both choices
Base case:
- If i >= n (reached or passed TOP), cost = 0
Special consideration:
- Can start from step 0 OR step 1
- So answer = min(climb(0), climb(1))
Recursion explores all possible paths!
📝 Implementation
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// Can start from step 0 or step 1
// Choose the one with minimum total cost
return Math.min(
minCost(0, cost), // Starting from step 0
minCost(1, cost) // Starting from step 1
);
}
private int minCost(int i, int[] cost) {
int n = cost.length;
// Base case: reached or passed the top
if (i >= n) {
return 0; // No more cost needed
}
// Pay cost at current step
int currentCost = cost[i];
// Explore both choices:
// Choice 1: Jump 1 step
int oneStep = minCost(i + 1, cost);
// Choice 2: Jump 2 steps
int twoSteps = minCost(i + 2, cost);
// Return: current cost + minimum of both choices
return currentCost + Math.min(oneStep, twoSteps);
}
}
🔍 Dry Run Example: cost = [10, 15, 20]
n = 3 (array length)
TOP = position 3 (beyond array)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Starting from step 0:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
minCost(0)
├─ cost[0] = 10
├─ min(minCost(1), minCost(2))
│ │
│ ├─ minCost(1)
│ │ ├─ cost[1] = 15
│ │ ├─ min(minCost(2), minCost(3))
│ │ │ │
│ │ │ ├─ minCost(2)
│ │ │ │ ├─ cost[2] = 20
│ │ │ │ ├─ min(minCost(3), minCost(4))
│ │ │ │ │ │
│ │ │ │ │ ├─ minCost(3) → i=3 >= n=3 → return 0
│ │ │ │ │ └─ minCost(4) → i=4 >= n=3 → return 0
│ │ │ │ │
│ │ │ │ ├─ min(0, 0) = 0
│ │ │ │ └─ return 20 + 0 = 20
│ │ │ │
│ │ │ └─ minCost(3) → i=3 >= n=3 → return 0
│ │ │
│ │ ├─ min(20, 0) = 0
│ │ └─ return 15 + 0 = 15
│ │
│ └─ minCost(2)
│ ├─ cost[2] = 20
│ ├─ min(minCost(3), minCost(4))
│ │ ├─ minCost(3) → return 0
│ │ └─ minCost(4) → return 0
│ ├─ min(0, 0) = 0
│ └─ return 20 + 0 = 20
│
├─ min(15, 20) = 15
└─ return 10 + 15 = 25
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Starting from step 1:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
minCost(1)
├─ cost[1] = 15
├─ min(minCost(2), minCost(3))
│ │
│ ├─ minCost(2)
│ │ └─ ... (calculated above) → return 20
│ │
│ └─ minCost(3) → return 0
│
├─ min(20, 0) = 0
└─ return 15 + 0 = 15
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Final answer: min(25, 15) = 15 ✓
NOTICE THE REPETITION:
- minCost(2) calculated MULTIPLE times! ⚠️
- minCost(3) calculated MULTIPLE times! ⚠️
This is WASTEFUL computation! 😰
📊 Complexity Analysis
Time Complexity: O(2^n)
Each call makes 2 recursive calls
Height of recursion tree ≈ n
Total calls ≈ 2^n (exponential!)
For n=3: ~8 calls
For n=10: ~1024 calls
For n=20: ~1,048,576 calls! 💥
Space Complexity: O(n)
Recursion stack depth ≈ n
Maximum n recursive calls on the stack
Why This Fails:
❌ Exponential time - too slow for n=1000
❌ Recalculates same subproblems multiple times
✅ But shows the recursive structure clearly!
🟡 Approach 2: Top-Down (Memoization)
💡 Intuition - The Clever Conversion
PROBLEM IDENTIFIED in Brute Force:
We keep recalculating minCost(2), minCost(3), etc.
SOLUTION:
Cache (memoize) results the FIRST time we calculate them
Next time we need same value → just look it up! 🎯
HOW TO IDENTIFY WHAT TO MEMOIZE:
1. Look at function parameters → minCost(i, cost)
2. Parameter 'i' changes with each recursive call
3. Same 'i' always gives same result (cost array doesn't change)
4. So memoize using 'i' as the key! 🔑
5. Key range: 0 to n (inclusive, since we can reach n)
CONVERSION FROM BRUTE FORCE:
1. Add a cache (array): memo[i] = min cost from step i
2. Before recursing, check: "Have I calculated minCost(i)?"
- If YES → return cached result
- If NO → calculate, store in cache, then return
3. That's it! Same logic, just add caching! ✨
🎯 Base Cases Transformation
BRUTE FORCE BASE CASES:
if (i >= n) return 0; // Reached or passed TOP
TOP-DOWN BASE CASES (SAME!):
if (i >= n) return 0; // Reached or passed TOP
Why same?
- Base cases define the termination condition
- "If we've reached or passed the top, no more cost needed"
- Memoization doesn't change the logic, only adds caching
ONLY ADDITIONS:
1. Create memo array of size (n+1) to handle index n
2. Initialize with -1 (meaning "not calculated yet")
3. Check cache before recursing
4. Store result in cache before returning
KEY INSIGHT:
Memo size is (n+1) because:
- We can be at positions 0, 1, 2, ..., n-1 (array indices)
- We can also reach position n (the TOP)
- So we need memo[0] through memo[n] = n+1 elements!
📝 Implementation
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// Create memoization cache
// memo[i] = minimum cost to reach TOP from step i
// Size (n+1) to handle index n (TOP position)
// Initialize with -1 (meaning "not calculated yet")
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
// Can start from step 0 or step 1
// Choose the one with minimum total cost
return Math.min(
minCost(0, cost, memo),
minCost(1, cost, memo)
);
}
private int minCost(int i, int[] cost, int[] memo) {
int n = cost.length;
// Base case: reached or passed the top (SAME as brute force)
if (i >= n) {
return 0;
}
// ✨ NEW: Check if already calculated
if (memo[i] != -1) {
return memo[i]; // Cache HIT! Return stored result
}
// Calculate (same recursive logic as brute force)
int currentCost = cost[i];
int oneStep = minCost(i + 1, cost, memo);
int twoSteps = minCost(i + 2, cost, memo);
// ✨ NEW: Store in cache before returning
memo[i] = currentCost + Math.min(oneStep, twoSteps);
return memo[i];
}
}
🔍 Detailed Dry Run: cost = [10, 15, 20]
Input: cost = [10, 15, 20]
n = 3
TOP = position 3
Initial State:
memo = [-1, -1, -1, -1] (size n+1 = 4)
↑ ↑ ↑ ↑
0 1 2 3 (indices, 3 is TOP)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TRY 1: Start from step 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: minCost(0)
Step 1: minCost(0)
i=0, not base case (0 < 3)
memo[0] = -1 → CACHE MISS
currentCost = cost[0] = 10
Need: min(minCost(1), minCost(2))
Recurse → minCost(1)
Step 2: minCost(1)
i=1, not base case (1 < 3)
memo[1] = -1 → CACHE MISS
currentCost = cost[1] = 15
Need: min(minCost(2), minCost(3))
Recurse → minCost(2)
Step 3: minCost(2)
i=2, not base case (2 < 3)
memo[2] = -1 → CACHE MISS
currentCost = cost[2] = 20
Need: min(minCost(3), minCost(4))
Recurse → minCost(3)
Step 4: minCost(3)
i=3 >= n=3 → BASE CASE
Return 0
Back to Step 3
Step 5: Back at minCost(2)
Got minCost(3) = 0
Now need minCost(4)
Recurse → minCost(4)
Step 6: minCost(4)
i=4 >= n=3 → BASE CASE
Return 0
Back to Step 5
Step 7: Back at minCost(2)
Got: minCost(3) = 0, minCost(4) = 0
Calculate: 20 + min(0, 0) = 20
Store: memo[2] = 20 ✓
Return 20
memo = [-1, -1, 20, -1]
↑
stored!
Back to Step 2
Step 8: Back at minCost(1)
Got minCost(2) = 20
Now need minCost(3)
Recurse → minCost(3)
Step 9: minCost(3)
i=3 >= n=3 → BASE CASE
Return 0
Back to Step 8
Step 10: Back at minCost(1)
Got: minCost(2) = 20, minCost(3) = 0
Calculate: 15 + min(20, 0) = 15 + 0 = 15
Store: memo[1] = 15 ✓
Return 15
memo = [-1, 15, 20, -1]
↑
stored!
Back to Step 1
Step 11: Back at minCost(0)
Got minCost(1) = 15
Now need minCost(2)
Check memo[2] = 20 → CACHE HIT! ✨
No recursion needed! Return 20 directly
This is where we SAVE time! 🎯
Step 12: Back at minCost(0)
Got: minCost(1) = 15, minCost(2) = 20
Calculate: 10 + min(15, 20) = 10 + 15 = 25
Store: memo[0] = 25 ✓
Return 25
memo = [25, 15, 20, -1]
↑
stored!
Result from starting at 0: 25
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TRY 2: Start from step 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: minCost(1)
Step 13: minCost(1)
Check memo[1] = 15 → CACHE HIT! ✨
Return 15 immediately!
No recursion needed - already calculated!
Result from starting at 1: 15
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Final memo = [25, 15, 20, -1]
↑ ↑ ↑
calculated values
Final answer: min(25, 15) = 15 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Cache Statistics:
Total unique subproblems: 3 (i = 0, 1, 2)
Cache MISSES (calculated): 3 (first time for each)
Cache HITS (reused): 2 (memo[2] once, memo[1] once)
Base cases (i >= 3): Called 3 times but instant return
Compare with Brute Force for n=3:
Brute Force: Would make ~16 recursive calls
Memoized: Made only ~9 calls (cache hits saved us!)
📊 Complexity Analysis
Time Complexity: O(n)
Each subproblem (0 to n-1) calculated EXACTLY ONCE
First time: calculate and store
Subsequent times: instant lookup from cache
Total unique subproblems = n
Time per subproblem = O(1)
Total time = O(n) ✓
Massive improvement from O(2^n)! 🚀
Space Complexity: O(n)
Memoization array: O(n+1) = O(n)
Recursion stack depth: O(n)
Total: O(n) + O(n) = O(n)
🟢 Approach 3: Bottom-Up (Tabulation)
💡 Intuition - The Clever Conversion from Top-Down
TOP-DOWN (Recursion + Memoization):
Start from step 0 or 1 → recurse to TOP → build back
minCost(0)
↓ needs
min(minCost(1), minCost(2))
↓ needs ↓ needs
(2)+(3) (3)+(4)
↓ ↓
reach TOP reach TOP
Direction: START → recurse to TOP, then back
BOTTOM-UP (Iteration + Tabulation):
Start from TOP → build backwards to start positions
dp[n] = 0 (at TOP, no cost)
↓ build backwards
dp[n-1] = cost[n-1] + min(dp[n], dp[n+1])
↓ build backwards
dp[n-2] = cost[n-2] + min(dp[n-1], dp[n])
↓ build backwards
...
↓ build backwards
dp[0], dp[1]
Direction: TOP → backwards to start
Wait, we can also build FORWARD! Let me explain both approaches:
APPROACH 1: Build backwards from TOP (intuitive from top-down)
dp[i] = minimum cost to reach TOP FROM step i
dp[i] = cost[i] + min(dp[i+1], dp[i+2])
Build: i = n-1 down to 0
APPROACH 2: Build forward from start (more common)
dp[i] = minimum cost to REACH step i
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
Build: i = 2 to n
We'll use APPROACH 2 (forward building) as it's more intuitive! 🎯
🎯 Base Cases Transformation - VERY IMPORTANT! 🔑
TOP-DOWN BASE CASES (in recursion):
if (i >= n) return 0; // At or past TOP
This is a TERMINATION condition:
"When we reach TOP, no more cost needed"
BOTTOM-UP BASE CASES (in DP table):
For forward building:
dp[i] = minimum cost to REACH step i
We can START from step 0 or step 1 for FREE!
So:
dp[0] = 0 (start here for free)
dp[1] = 0 (start here for free)
Wait, that doesn't match top-down! Let me clarify:
KEY INSIGHT - THE CLEVER THINKING:
Top-down: dp[i] = min cost to reach TOP FROM step i
Bottom-up: dp[i] = min cost to REACH step i
These are DIFFERENT meanings! But lead to same answer!
Top-down thinks: "From here, how much to reach TOP?"
Bottom-up thinks: "To get here, what's the min cost?"
CONVERSION PROCESS:
1. Change perspective from "reach TOP from i" to "reach i"
2. Base cases become: dp[0]=0, dp[1]=0 (free to start)
3. Recurrence changes:
Top-down: dp[i] = cost[i] + min(dp[i+1], dp[i+2])
Bottom-up: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
4. Answer changes:
Top-down: min(dp[0], dp[1])
Bottom-up: dp[n] (cost to reach TOP)
EXAMPLE:
cost = [10, 15, 20]
Top-down thinking:
From step 0: need 10 + (min cost from step 1 or 2) to TOP
From step 1: need 15 + (min cost from step 2 or 3) to TOP
From step 2: need 20 + (min cost from step 3 or 4) to TOP
Bottom-up thinking:
To reach step 0: 0 (free start)
To reach step 1: 0 (free start)
To reach step 2: min(reach 0 + cost[0], reach 1 + cost[1])
To reach TOP: min(reach n-1 + cost[n-1], reach n-2 + cost[n-2])
Same problem, different perspective! 🎯
🔄 Recurrence Relation
Definition:
dp[i] = minimum cost to REACH step i
To reach step i, we can come from:
- Step (i-1): pay cost[i-1], jump 1 step → reach i
- Step (i-2): pay cost[i-2], jump 2 steps → reach i
So:
dp[i] = min(
dp[i-1] + cost[i-1], // via step i-1
dp[i-2] + cost[i-2] // via step i-2
)
Dependencies:
dp[i-2] dp[i-1]
↓ ↓
cost[i-2] cost[i-1]
↓ ↓
└────────┬───────────┘
↓
dp[i]
Must calculate in order: 0, 1, 2, 3, ..., n
Can't skip ahead! Must build sequentially! 🎯
📝 Implementation
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// Create DP table
// dp[i] = minimum cost to REACH step i
// Size (n+1) because TOP is at position n (beyond array)
int[] dp = new int[n + 1];
// Initialize base cases (VERY IMPORTANT!)
// Can start from step 0 or step 1 for FREE
dp[0] = 0; // Free to start at step 0
dp[1] = 0; // Free to start at step 1
// Build up from base cases to TOP
// Start from 2 because we already know dp[0] and dp[1]
for (int i = 2; i <= n; i++) {
// To reach step i, choose minimum of:
// 1. From step i-1: dp[i-1] + cost[i-1]
// 2. From step i-2: dp[i-2] + cost[i-2]
dp[i] = Math.min(
dp[i - 1] + cost[i - 1], // via step i-1
dp[i - 2] + cost[i - 2] // via step i-2
);
}
// Answer is at dp[n] (minimum cost to reach TOP)
return dp[n];
}
}
🔍 Detailed Dry Run: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
0 1 2 3 4 5 6 7 8 9 (indices)
n = 10
TOP = position 10 (beyond array)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Create DP table:
dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (size n+1 = 11)
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
0 1 2 3 4 5 6 7 8 9 10 (indices, 10 is TOP)
Initialize base cases:
dp[0] = 0 (free to start at step 0)
dp[1] = 0 (free to start at step 1)
dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
↑ ↑
base cases ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Building up to TOP
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i = 2
━━━━━━━━━━━━━━━━
To reach step 2:
Option 1: dp[1] + cost[1] = 0 + 100 = 100
Option 2: dp[0] + cost[0] = 0 + 1 = 1 ✓
dp[2] = min(100, 1) = 1
Meaning: To reach step 2, better to:
Come from step 0, pay 1, jump 2 steps
dp = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
↑
Iteration 2: i = 3
━━━━━━━━━━━━━━━━
To reach step 3:
Option 1: dp[2] + cost[2] = 1 + 1 = 2 ✓
Option 2: dp[1] + cost[1] = 0 + 100 = 100
dp[3] = min(2, 100) = 2
dp = [0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0]
↑
Iteration 3: i = 4
━━━━━━━━━━━━━━━━
To reach step 4:
Option 1: dp[3] + cost[3] = 2 + 1 = 3 ✓
Option 2: dp[2] + cost[2] = 1 + 1 = 2 ✓✓
dp[4] = min(3, 2) = 2
dp = [0, 0, 1, 2, 2, 0, 0, 0, 0, 0, 0]
↑
Iteration 4: i = 5
━━━━━━━━━━━━━━━━
To reach step 5:
Option 1: dp[4] + cost[4] = 2 + 1 = 3 ✓
Option 2: dp[3] + cost[3] = 2 + 1 = 3 ✓
dp[5] = min(3, 3) = 3
dp = [0, 0, 1, 2, 2, 3, 0, 0, 0, 0, 0]
↑
Iteration 5: i = 6
━━━━━━━━━━━━━━━━
To reach step 6:
Option 1: dp[5] + cost[5] = 3 + 100 = 103
Option 2: dp[4] + cost[4] = 2 + 1 = 3 ✓
dp[6] = min(103, 3) = 3
dp = [0, 0, 1, 2, 2, 3, 3, 0, 0, 0, 0]
↑
Iteration 6: i = 7
━━━━━━━━━━━━━━━━
To reach step 7:
Option 1: dp[6] + cost[6] = 3 + 1 = 4 ✓
Option 2: dp[5] + cost[5] = 3 + 100 = 103
dp[7] = min(4, 103) = 4
dp = [0, 0, 1, 2, 2, 3, 3, 4, 0, 0, 0]
↑
Iteration 7: i = 8
━━━━━━━━━━━━━━━━
To reach step 8:
Option 1: dp[7] + cost[7] = 4 + 1 = 5 ✓
Option 2: dp[6] + cost[6] = 3 + 1 = 4 ✓✓
dp[8] = min(5, 4) = 4
dp = [0, 0, 1, 2, 2, 3, 3, 4, 4, 0, 0]
↑
Iteration 8: i = 9
━━━━━━━━━━━━━━━━
To reach step 9:
Option 1: dp[8] + cost[8] = 4 + 100 = 104
Option 2: dp[7] + cost[7] = 4 + 1 = 5 ✓
dp[9] = min(104, 5) = 5
dp = [0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 0]
↑
Iteration 9: i = 10 (TOP - FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
To reach TOP (step 10):
Option 1: dp[9] + cost[9] = 5 + 1 = 6 ✓
Option 2: dp[8] + cost[8] = 4 + 100 = 104
dp[10] = min(6, 104) = 6
Final DP table:
dp = [0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6]
↑
ANSWER!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPLETE DP TABLE VISUALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Index: 0 1 2 3 4 5 6 7 8 9 10
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬───┐
dp[] │0 │0 │1 │2 │2 │3 │3 │4 │4 │5 │ 6 │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴───┘
↑ ↑ ↑
free free Answer
start
Cost: 1 100 1 1 1 100 1 1 100 1
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
0 1 2 3 4 5 6 7 8 9
Notice: We avoid all the expensive steps (100)!
Path: 0 → 2 → 4 → 6 → 8 → 10
Costs paid: 1, 1, 1, 1, 1 = 6 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 6 (minimum cost to reach TOP) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
📊 State Transition Diagram
dp[i] depends on TWO previous states with their costs:
┌────────────────┐
│ dp[i-2] │
│ (2 steps back) │
└───────┬────────┘
│ + cost[i-2]
│
├─────────────┐
│ │
↓ ↓
┌───────────┐ ┌──────────┐
│ dp[i-1] │ │ dp[i] │
│ (1 step │→ │(current) │
│ back) │ └──────────┘
└─────┬─────┘
│ + cost[i-1]
Formula: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
Example for dp[4]:
cost = [1, 100, 1, 1, ...]
dp[4] = min(dp[3] + cost[3], dp[2] + cost[2])
= min(2 + 1, 1 + 1)
= min(3, 2)
= 2 ✓
Choose the cheaper path! 🎯
📊 Complexity Analysis
Time Complexity: O(n)
Single loop from 2 to n
Each iteration: O(1) work (just comparison and addition)
Total: O(n) ✓
Same as top-down, but:
- No recursion overhead
- No function call overhead
- Slightly faster in practice! ⚡
Space Complexity: O(n)
DP table of size (n+1): O(n)
No recursion stack: O(1)
Total: O(n)
🔵 Approach 4: Space-Optimized Bottom-Up
💡 Intuition - Reducing Space
OBSERVATION from Bottom-Up approach:
To calculate dp[i], we only need:
- dp[i-1] (previous position)
- dp[i-2] (position before previous)
- cost[i-1] and cost[i-2] (from input array)
We DON'T need dp[0], dp[1], ..., dp[i-3]!
Example: When calculating dp[6]:
dp[6] = min(dp[5] + cost[5], dp[4] + cost[4])
↑ ↑
only need these two!
Don't need: dp[0], dp[1], dp[2], dp[3]
INSIGHT:
Instead of array of size (n+1), use just TWO variables! 🎯
prev2 = dp[i-2] (value from 2 steps back)
prev1 = dp[i-1] (value from 1 step back)
current = min(prev1 + cost[i-1], prev2 + cost[i-2])
Then shift:
prev2 = prev1
prev1 = current
Repeat! 🔄
SPACE REDUCTION:
O(n) array → O(1) variables
Massive space savings for large n! 🚀
📝 Implementation
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
// Instead of array, use two variables
// These represent dp[i-2] and dp[i-1]
int prev2 = 0; // dp[0] - free to start at step 0
int prev1 = 0; // dp[1] - free to start at step 1
// Build up from base cases to TOP
for (int i = 2; i <= n; i++) {
// Calculate current value
int current = Math.min(
prev1 + cost[i - 1], // via step i-1
prev2 + cost[i - 2] // via step i-2
);
// Shift values for next iteration
prev2 = prev1; // What was dp[i-1] becomes dp[i-2]
prev1 = current; // What we just calculated becomes dp[i-1]
}
// prev1 now holds dp[n] (minimum cost to reach TOP)
return prev1;
}
}
🔍 Detailed Dry Run: cost = [10, 15, 20]
Input: cost = [10, 15, 20]
n = 3
TOP = position 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Variables (instead of array):
prev2 = 0 (represents dp[0])
prev1 = 0 (represents dp[1])
Visual state (what these represent):
prev2 prev1
↓ ↓
[0] [0] [?] [?]
0 1 2 3 (TOP)
We'll calculate positions 2→3 using just these 2 variables!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i = 2
━━━━━━━━━━━━━━━━
Before:
prev2 = 0, prev1 = 0
Calculate current (dp[2]):
Option 1: prev1 + cost[1] = 0 + 15 = 15
Option 2: prev2 + cost[0] = 0 + 10 = 10 ✓
current = min(15, 10) = 10
Meaning: To reach step 2, better to:
Start from step 0, pay 10, jump 2 steps
Shift values:
prev2 = prev1 = 0
prev1 = current = 10
After:
prev2 = 0, prev1 = 10
Visual state:
prev2 prev1
↓ ↓
[0] [0] [10] [?]
0 1 2 3
Iteration 2: i = 3 (TOP - FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Before:
prev2 = 0, prev1 = 10
Calculate current (dp[3] - minimum cost to reach TOP):
Option 1: prev1 + cost[2] = 10 + 20 = 30
Option 2: prev2 + cost[1] = 0 + 15 = 15 ✓
current = min(30, 15) = 15
Meaning: To reach TOP, better to:
Start from step 1 (free), pay 15, jump 2 steps to TOP
Shift values:
prev2 = prev1 = 10
prev1 = current = 15
After:
prev2 = 10, prev1 = 15
Visual state:
prev2 prev1
↓ ↓
[0] [0] [10] [15]
0 1 2 3 (TOP)
↑
ANSWER!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
VARIABLE EVOLUTION TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i │ prev2 │ prev1 │ current │ Calculation
───┼───────┼───────┼─────────┼─────────────────────────
- │ 0 │ 0 │ - │ Initialization
2 │ 0 │ 0 │ 10 │ min(0+15, 0+10) = 10
3 │ 0 │ 10 │ 15 │ min(10+20, 0+15) = 15
Final: prev1 = 15
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 15 (minimum cost to reach TOP) ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Optimal Path Traced:
Start at step 1 (free)
Pay 15 at step 1
Jump 2 steps → reach TOP
Total cost: 15 ✓
Space used: Only 3 integer variables!
- prev2
- prev1
- current (temporary)
Compare with bottom-up array: Would need array of size 4!
Space reduction: O(n) → O(1) 🎯
📊 Complexity Analysis
Time Complexity: O(n)
Single loop from 2 to n
Each iteration: O(1) work
Total: O(n) ✓
Same as previous approaches
Space Complexity: O(1) ⭐
Only 3 variables used:
- prev2
- prev1
- current (temporary)
No array, no recursion stack
Constant space! 🚀
MASSIVE improvement from O(n)!
For n=1000: Saves ~4KB of memory!
🎯 Pattern Recognition - Min Cost Optimization DP
Core Pattern: Choose Minimum Path
Template for optimization DP problems:
dp[i] = min/max(
option1 + some_cost,
option2 + some_cost,
...
)
For Min Cost Climbing Stairs:
dp[i] = min(
dp[i-1] + cost[i-1], // via previous step
dp[i-2] + cost[i-2] // via 2 steps back
)
Similar Problems:
- House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- Minimum Path Sum: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
- Jump Game II: dp[i] = min(dp[i], dp[j] + 1) for all valid j
How to Identify Optimization DP:
✅ Problem asks for "minimum" or "maximum"
✅ Multiple ways to reach same state
✅ Need to choose optimal among options
✅ Current state depends on previous states
✅ Optimal substructure exists
For Min Cost Climbing Stairs:
✅ Find "minimum cost"
✅ Can reach step i from i-1 or i-2
✅ Choose cheaper option
✅ Depends on optimal costs to i-1 and i-2
✅ Optimal solution uses optimal subproblems
Perfect for Optimization DP! 🎯
📝 Quick Revision Notes
🎯 Core Concept
Problem: Find minimum cost to reach top of stairs. Each step has cost. Can climb 1 or 2 steps after paying cost. Can start from step 0 or 1.
Key Insight: To reach position i, choose minimum of: (cost to reach i-1 + cost[i-1]) or (cost to reach i-2 + cost[i-2]). Formula: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
Four Approaches: 1. Brute Force: Recursion exploring all paths → O(2^n) time ❌ 2. Top-Down: Add memoization to cache results → O(n) time, O(n) space ✓ 3. Bottom-Up: Iterative DP table building → O(n) time, O(n) space ✓✓ 4. Space-Optimized: Keep only 2 variables → O(n) time, O(1) space ⭐
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int minCostClimbingStairs(int[] cost) {
// // Approach 1 - recursion
// return Math.min(recursive(0, cost), recursive(1, cost));
// Approach 2 - top down
int[] memo = new int[cost.length + 1];
Arrays.fill(memo, -1);
return Math.min(topDown(0, cost, memo), topDown(1, cost, memo));
// // Approach 3 - bottom up
// return bottomUp(cost);
// // Approach 4 - bottom up space optimized
// return bottomUpSO(cost);
}
private int bottomUpSO(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
// base cases
int prev1 = 0; // we start from step 0. Cost is free here.
int prev2 = 0; // we start from step 1. Cost is free here.
for (int i = 2; i <= n; i++) {
// you could have come to ith step either from (i-1) or (i-2) steps.
// For example, dp[2] = dp[0] + dp[1]
// So, if you start from step 0, pay for step 0 and start/try.
// Similarly, if you start from step 1, pay for that step and start/try.
dp[i] = Math.min(prev2 + cost[i - 1], prev1 + cost[i - 2]);
prev1 = dp[i - 1];
prev2 = dp[i];
}
return dp[n];
}
private int bottomUp(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
// base cases
dp[0] = 0; // we start from step 0. Cost is free here.
dp[1] = 0; // we start from step 1. Cost is free here.
for (int i = 2; i <= n; i++) {
// you could have come to ith step either from (i-1) or (i-2) steps.
// For example, dp[2] = dp[0] + dp[1]
// So, if you start from step 0, pay for step 0 and start/try.
// Similarly, if you start from step 1, pay for that step and start/try.
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
private int topDown(int currStep, int[] cost, int[] memo) {
// same base case
if (currStep >= cost.length) {
return 0;
}
// memo step added
if (memo[currStep] != -1) {
return memo[currStep];
}
return memo[currStep] = cost[currStep]
+ Math.min(topDown(currStep + 1, cost, memo), topDown(currStep + 2, cost, memo));
}
private int recursive(int currStep, int[] cost) {
// base case
if (currStep >= cost.length) {
return 0;
}
return cost[currStep] + Math.min(recursive(currStep + 1, cost), recursive(currStep + 2, cost));
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minCostClimbingStairs(new int[] { 10, 15, 20 }));
System.out.println(s.minCostClimbingStairs(new int[] { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 }));
}
}
🔑 Key Insights
Base Cases:
dp[0] = 0 (free to start at step 0)
dp[1] = 0 (free to start at step 1)
WHY both are 0?
Problem says "start from index 0 OR index 1"
No cost to START - only cost to CLIMB from there
So both starting positions are free! 🎯
Recurrence Relation:
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
WHY?
To reach position i, we can either:
- Be at i-1, pay cost[i-1], jump 1 step
- Be at i-2, pay cost[i-2], jump 2 steps
Choose the CHEAPER option! 💰
TOP Position:
TOP is at position n (beyond last step)
cost = [10, 15, 20] (n=3)
↑ ↑ ↑
0 1 2 (indices)
↑
TOP (position 3)
Must reach position 3, not stop at position 2!
Difference from Climbing Stairs:
Problem 205 (Climbing Stairs):
ways(n) = ways(n-1) + ways(n-2)
SUM both options (counting)
Problem 206 (Min Cost):
dp[i] = MIN(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
MIN of options (optimization)
Pattern evolution: COUNT → OPTIMIZE 🎯
🎪 Memory Aid
"Start free, climb with cost!"
"Choose cheaper path!"
"TOP is beyond last step!"
"MIN not SUM - optimization!" ✨
⚠️ Common Mistakes
- ❌ Setting dp[0] = cost[0] or dp[1] = cost[1] (both should be 0!)
- ❌ Thinking TOP is at index n-1 (it's at position n!)
- ❌ Using SUM instead of MIN (this is optimization, not counting!)
- ❌ Forgetting cost[i-1] and cost[i-2] in recurrence
- ❌ Starting loop from i=0 instead of i=2
✅ Interview Talking Points
"This is an optimization DP problem - we need minimum cost.
Key differences from basic Climbing Stairs:
1. Each step has a cost
2. We want minimum total cost, not count of ways
3. Use MIN instead of SUM in recurrence
4. TOP is position n (beyond array)
Approach:
1. Base cases: dp[0]=0, dp[1]=0 (free to start)
2. Recurrence: dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
3. Build from positions 2 to n
4. Optimize to O(1) space with two variables
Why DP?
- Overlapping subproblems (dp[i] needed multiple times)
- Optimal substructure (optimal answer uses optimal subproblems)
- Need to explore all paths to find true minimum
Complexity: O(n) time, O(1) space with optimization"
🎉 Congratulations!
You've mastered Min Cost Climbing Stairs - optimization DP pattern!
What You Learned:
✅ Optimization DP - MIN/MAX instead of counting
✅ Cost-based recurrence - Including step costs in formula
✅ TOP position - Target beyond array boundary
✅ Free start - Both start positions have 0 cost
✅ Pattern evolution - From counting (205) to optimization (206)
✅ Space optimization - O(n) to O(1) reduction
The Beautiful Connection:
Problem 205 (Climbing Stairs):
COUNT distinct ways
ways(n) = ways(n-1) + ways(n-2)
Operation: SUM (add both options)
Problem 206 (Min Cost Climbing):
MINIMIZE total cost
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
Operation: MIN (choose cheaper option)
SAME STRUCTURE, DIFFERENT OPERATION! 🎯
This pattern appears in MANY problems:
- House Robber (MAX with constraint)
- Minimum Path Sum (MIN in 2D grid)
- Jump Game variations (MIN jumps)
Master this = Master optimization DP! 💪
You've now completed 2 foundational 1D DP problems! Ready for more? 🚀✨