205. Climbing Stairs
🔗 LeetCode Problem: 70. Climbing Stairs
📊 Difficulty: Easy
🏷️ Topics: Dynamic Programming, Math, Memoization, 1D DP
Problem Statement
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Example 3:
Input: n = 4
Output: 5
Explanation: There are five ways to climb to the top.
1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2
Constraints:
- 1 <= n <= 45
🌳 Visual Understanding - The Staircase Problem
The Problem We're Solving:
Given: A staircase with n steps
Goal: Count DISTINCT ways to reach the top
Rules: Can climb 1 or 2 steps at a time
Example: n = 4
Ground ──────────┐
│
Step 1 ──────────┤
│ Can take 1 step OR 2 steps
Step 2 ──────────┤ at each position
│
Step 3 ──────────┤
│
Step 4 (TOP) ────┘
How many different paths from Ground → Step 4? 🤔
All Possible Ways for n = 4:
Way 1: 1 + 1 + 1 + 1
━━━━━━━━━━━━━━━━━━━━━━━
Ground → 1 → 2 → 3 → 4
↑ ↑ ↑ ↑
+1 +1 +1 +1
Way 2: 1 + 1 + 2
━━━━━━━━━━━━━━━━━━━━━━━
Ground → 1 → 2 ──→ 4
↑ ↑ ↑
+1 +1 +2
Way 3: 1 + 2 + 1
━━━━━━━━━━━━━━━━━━━━━━━
Ground → 1 ──→ 3 → 4
↑ ↑ ↑
+1 +2 +1
Way 4: 2 + 1 + 1
━━━━━━━━━━━━━━━━━━━━━━━
Ground ──→ 2 → 3 → 4
↑ ↑ ↑
+2 +1 +1
Way 5: 2 + 2
━━━━━━━━━━━━━━━━━━━━━━━
Ground ──→ 2 ──→ 4
↑ ↑
+2 +2
Total: 5 distinct ways! ✅
🧠 The AHA Moment - Why Dynamic Programming?
The Key Observation:
Standing at step 4, how did we get here?
Step 3 Step 2
│ │
│ +1 step │ +2 steps
└────────→ Step 4 ←────────┘
INSIGHT: To reach step 4, we MUST have come from:
- Step 3 (by taking 1 step), OR
- Step 2 (by taking 2 steps)
No other way! 🔑
So: ways(4) = ways(3) + ways(2)
The Pattern Emerges:
Let's work backwards from the top:
To reach step n, we came from:
- Step (n-1) by taking 1 step, OR
- Step (n-2) by taking 2 steps
Formula: ways(n) = ways(n-1) + ways(n-2)
This is the FIBONACCI pattern! 🎯
Example for n=4:
ways(4) = ways(3) + ways(2)
ways(3) = ways(2) + ways(1)
ways(2) = ways(1) + ways(0)
ways(1) = 1 (base case: only one way - take 1 step)
ways(0) = 1 (base case: already at ground, 1 way to stay)
Let's verify:
ways(0) = 1
ways(1) = 1
ways(2) = ways(1) + ways(0) = 1 + 1 = 2
ways(3) = ways(2) + ways(1) = 2 + 1 = 3
ways(4) = ways(3) + ways(2) = 3 + 2 = 5 ✓
Why Not Greedy?
Greedy approach: "Always take 2 steps when possible"
Ground → 2 → 4 (Done in 2 moves)
But this only finds ONE way, not COUNT of all ways!
We need to explore ALL possibilities:
- What if we take 1 step first?
- What if we take 2 steps first?
- From each new position, what are ALL ways?
This is a COUNTING problem, not OPTIMIZATION! 🎯
Greedy won't work - need to explore all paths!
Why Dynamic Programming?
1. OVERLAPPING SUBPROBLEMS:
To find ways(5), we need ways(4) and ways(3)
To find ways(4), we need ways(3) and ways(2)
Notice: ways(3) is needed TWICE! ⚠️
Without memoization, we recalculate it multiple times!
2. OPTIMAL SUBSTRUCTURE:
ways(n) can be built from smaller subproblems
ways(n) = ways(n-1) + ways(n-2)
Solution to larger problem uses solutions to smaller ones!
These TWO properties = Perfect for DP! 🎯
🔴 Approach 1: Brute Force (Recursion)
💡 Intuition
Simple idea: At each step, we have 2 choices:
1. Take 1 step → solve for (n-1) remaining steps
2. Take 2 steps → solve for (n-2) remaining steps
Total ways = ways from choice 1 + ways from choice 2
Recursion naturally explores all paths!
Base cases:
- n = 0: Already at top (1 way - do nothing)
- n = 1: Only 1 way (take 1 step)
📝 Implementation
class Solution {
public int climbStairs(int n) {
// Base cases
if (n == 0) return 1; // Already at top
if (n == 1) return 1; // Only one way: take 1 step
// Recursive case: explore both choices
// Choice 1: Take 1 step, solve for (n-1)
int oneStep = climbStairs(n - 1);
// Choice 2: Take 2 steps, solve for (n-2)
int twoSteps = climbStairs(n - 2);
// Total ways = sum of both choices
return oneStep + twoSteps;
}
}
🔍 Dry Run Example: n = 4
climbStairs(4)
├─ climbStairs(3)
│ ├─ climbStairs(2)
│ │ ├─ climbStairs(1) → 1
│ │ └─ climbStairs(0) → 1
│ │ = 1 + 1 = 2
│ └─ climbStairs(1) → 1
│ = 2 + 1 = 3
└─ climbStairs(2)
├─ climbStairs(1) → 1
└─ climbStairs(0) → 1
= 1 + 1 = 2
= 3 + 2 = 5 ✓
Notice the REPETITION:
- climbStairs(2) calculated TWICE! ⚠️
- climbStairs(1) calculated THREE times! ⚠️
- climbStairs(0) calculated TWICE! ⚠️
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=4: ~16 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=45
❌ 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 climbStairs(2), climbStairs(1), 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 → climbStairs(n)
2. Parameter 'n' changes with each recursive call
3. Same 'n' gives same result (pure function)
4. So memoize using 'n' as the key! 🔑
CONVERSION FROM BRUTE FORCE:
1. Add a cache (array/map): memo[n]
2. Before recursing, check: "Have I solved this before?"
- 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 (n == 0) return 1;
if (n == 1) return 1;
TOP-DOWN BASE CASES (SAME!):
if (n == 0) return 1;
if (n == 1) return 1;
Why same?
- Base cases define the termination condition
- They don't change when we add memoization
- Memoization only affects HOW we calculate, not WHAT we calculate
ONLY ADDITION:
- Check cache before recursing
- Store result in cache before returning
📝 Implementation
class Solution {
public int climbStairs(int n) {
// Create memoization cache
// memo[i] = number of ways to reach step i
// Initialize with -1 (meaning "not calculated yet")
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return climbStairsHelper(n, memo);
}
private int climbStairsHelper(int n, int[] memo) {
// Base cases (SAME as brute force)
if (n == 0) return 1;
if (n == 1) return 1;
// ✨ NEW: Check if already calculated
if (memo[n] != -1) {
return memo[n]; // Cache HIT! Return stored result
}
// Calculate (same recursive logic as brute force)
int oneStep = climbStairsHelper(n - 1, memo);
int twoSteps = climbStairsHelper(n - 2, memo);
// ✨ NEW: Store in cache before returning
memo[n] = oneStep + twoSteps;
return memo[n];
}
}
🔍 Detailed Dry Run: n = 5
Initial State:
memo = [-1, -1, -1, -1, -1, -1] (indices 0 to 5)
↑ ↑ ↑ ↑ ↑ ↑
0 1 2 3 4 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Call: climbStairs(5)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: climbStairs(5)
n=5, not base case
memo[5] = -1 (not calculated) → CACHE MISS
Need: climbStairs(4) + climbStairs(3)
Recurse → climbStairs(4)
Step 2: climbStairs(4)
n=4, not base case
memo[4] = -1 (not calculated) → CACHE MISS
Need: climbStairs(3) + climbStairs(2)
Recurse → climbStairs(3)
Step 3: climbStairs(3)
n=3, not base case
memo[3] = -1 (not calculated) → CACHE MISS
Need: climbStairs(2) + climbStairs(1)
Recurse → climbStairs(2)
Step 4: climbStairs(2)
n=2, not base case
memo[2] = -1 (not calculated) → CACHE MISS
Need: climbStairs(1) + climbStairs(0)
Recurse → climbStairs(1)
Step 5: climbStairs(1)
n=1 → BASE CASE
Return 1
Back to Step 4
Step 6: Back at climbStairs(2)
Got climbStairs(1) = 1
Now need climbStairs(0)
Recurse → climbStairs(0)
Step 7: climbStairs(0)
n=0 → BASE CASE
Return 1
Back to Step 6
Step 8: Back at climbStairs(2)
Got: climbStairs(1) = 1, climbStairs(0) = 1
Calculate: 1 + 1 = 2
Store: memo[2] = 2 ✓
Return 2
memo = [-1, -1, 2, -1, -1, -1]
↑
stored!
Back to Step 3
Step 9: Back at climbStairs(3)
Got climbStairs(2) = 2
Now need climbStairs(1)
Recurse → climbStairs(1)
Step 10: climbStairs(1)
n=1 → BASE CASE
Return 1
Back to Step 9
Step 11: Back at climbStairs(3)
Got: climbStairs(2) = 2, climbStairs(1) = 1
Calculate: 2 + 1 = 3
Store: memo[3] = 3 ✓
Return 3
memo = [-1, -1, 2, 3, -1, -1]
↑
stored!
Back to Step 2
Step 12: Back at climbStairs(4)
Got climbStairs(3) = 3
Now need climbStairs(2)
Check memo[2] = 2 → CACHE HIT! ✨
No recursion needed! Return 2 directly
This is where we SAVE time! 🎯
Step 13: Back at climbStairs(4)
Got: climbStairs(3) = 3, climbStairs(2) = 2
Calculate: 3 + 2 = 5
Store: memo[4] = 5 ✓
Return 5
memo = [-1, -1, 2, 3, 5, -1]
↑
stored!
Back to Step 1
Step 14: Back at climbStairs(5)
Got climbStairs(4) = 5
Now need climbStairs(3)
Check memo[3] = 3 → CACHE HIT! ✨
No recursion needed! Return 3 directly
Step 15: Back at climbStairs(5)
Got: climbStairs(4) = 5, climbStairs(3) = 3
Calculate: 5 + 3 = 8
Store: memo[5] = 8 ✓
Return 8
Final memo = [-1, -1, 2, 3, 5, 8]
↑ ↑ ↑
calculated values
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 8 ways to climb 5 steps! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Cache Hits vs Misses:
Total unique subproblems: 6 (n = 0,1,2,3,4,5)
Cache MISSES (calculated): 4 (n = 2,3,4,5)
Cache HITS (reused): 2 (n = 2 once, n = 3 once)
Base cases (n=0,1): 3 times called but instant return
Compare with Brute Force for n=5:
Brute Force: Would make ~32 recursive calls
Memoized: Made only ~9 calls (cache hits saved us!)
📊 Complexity Analysis
Time Complexity: O(n)
Each subproblem (0 to n) 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)
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 n → recurse down to base cases → build up
climbStairs(5)
↓ needs
climbStairs(4) + climbStairs(3)
↓ needs ↓ needs
(3)+(2) (2)+(1)
Direction: TOP → DOWN to bases, then back UP
BOTTOM-UP (Iteration + Tabulation):
Start from base cases → build up to n iteratively
dp[0]=1, dp[1]=1 (base cases)
↓ build
dp[2] = dp[1] + dp[0]
↓ build
dp[3] = dp[2] + dp[1]
↓ build
...
↓ build
dp[n]
Direction: BOTTOM (bases) → UP to n
WHY BOTTOM-UP IS BETTER:
✅ No recursion → no stack space overhead
✅ No function call overhead → slightly faster
✅ Easier to optimize space later
✅ More intuitive once you see the pattern
🎯 Base Cases Transformation - VERY IMPORTANT! 🔑
TOP-DOWN BASE CASES (in recursion):
if (n == 0) return 1;
if (n == 1) return 1;
These are TERMINATION conditions
When we hit these during recursion, we return immediately
BOTTOM-UP BASE CASES (in DP table):
dp[0] = 1;
dp[1] = 1;
These are INITIALIZATION values
We START with these, then build UP from them
KEY INSIGHT - THE CLEVER THINKING:
1. In top-down: "What do I return when I can't recurse further?"
→ That becomes your base case
2. In bottom-up: "What are the smallest subproblems I know?"
→ Initialize DP table with those values
3. The VALUES are the same, but the ROLE is different:
- Top-down: BASE = where recursion STOPS
- Bottom-up: BASE = where iteration STARTS
EXAMPLE:
Top-down: if (n == 0) return 1;
↓
Bottom-up: dp[0] = 1;
Same value (1), different purpose! 🎯
HOW TO CONVERT:
Step 1: Identify base cases from top-down
Step 2: Initialize DP table with these values
Step 3: Start iteration from next position
For Climbing Stairs:
Base cases: dp[0]=1, dp[1]=1
Start loop from i=2 (next position after bases)
Loop until i=n
🔄 Recurrence Relation
From top-down, we know:
ways(n) = ways(n-1) + ways(n-2)
In bottom-up DP table notation:
dp[i] = dp[i-1] + dp[i-2]
Where:
dp[i] = number of ways to reach step i
Dependencies:
dp[i] depends on dp[i-1] and dp[i-2]
dp[i-2] dp[i-1]
↓ ↓
└────┬───┘
↓
dp[i]
So we must calculate in order: 0, 1, 2, 3, ..., n
Can't skip ahead! Must build sequentially! 🎯
📝 Implementation
class Solution {
public int climbStairs(int n) {
// Edge case: if n is 0 or 1, return 1
if (n <= 1) return 1;
// Create DP table
// dp[i] = number of ways to reach step i
int[] dp = new int[n + 1];
// Initialize base cases (VERY IMPORTANT!)
// These are our starting point - smallest known subproblems
dp[0] = 1; // 0 steps: 1 way (do nothing)
dp[1] = 1; // 1 step: 1 way (take one 1-step)
// Build up from base cases to n
// Start from 2 because we already know dp[0] and dp[1]
for (int i = 2; i <= n; i++) {
// Recurrence relation
dp[i] = dp[i - 1] + dp[i - 2];
// ↑ ↑ ↑
// | | └─ ways from 2 steps before
// | └─ ways from 1 step before
// └─ total ways to reach step i
}
// Answer is at dp[n]
return dp[n];
}
}
🔍 Detailed Dry Run: n = 6
Input: n = 6
Goal: Find number of ways to climb 6 steps
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Create DP table:
dp = [0, 0, 0, 0, 0, 0, 0] (size n+1 = 7)
↑ ↑ ↑ ↑ ↑ ↑ ↑
0 1 2 3 4 5 6
Initialize base cases:
dp[0] = 1 (0 steps: already at top, 1 way)
dp[1] = 1 (1 step: only one way - take 1 step)
dp = [1, 1, 0, 0, 0, 0, 0]
↑ ↑
base cases initialized ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Building up to n
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i = 2
━━━━━━━━━━━━━━━━
Calculate dp[2]:
dp[2] = dp[1] + dp[0]
= 1 + 1
= 2
Meaning: To reach step 2, we can:
- Come from step 1 (1 way) + take 1 step
- Come from step 0 (1 way) + take 2 steps
Total: 2 ways
dp = [1, 1, 2, 0, 0, 0, 0]
↑
calculated!
Visual dependency:
dp[0]=1 dp[1]=1
↓ ↓
└────┬───┘
↓
dp[2]=2
Iteration 2: i = 3
━━━━━━━━━━━━━━━━
Calculate dp[3]:
dp[3] = dp[2] + dp[1]
= 2 + 1
= 3
Meaning: To reach step 3, we can:
- Come from step 2 (2 ways) + take 1 step
- Come from step 1 (1 way) + take 2 steps
Total: 3 ways
dp = [1, 1, 2, 3, 0, 0, 0]
↑
calculated!
Visual dependency:
dp[1]=1 dp[2]=2
↓ ↓
└────┬───┘
↓
dp[3]=3
Iteration 3: i = 4
━━━━━━━━━━━━━━━━
Calculate dp[4]:
dp[4] = dp[3] + dp[2]
= 3 + 2
= 5
Meaning: To reach step 4, we can:
- Come from step 3 (3 ways) + take 1 step
- Come from step 2 (2 ways) + take 2 steps
Total: 5 ways
dp = [1, 1, 2, 3, 5, 0, 0]
↑
calculated!
Visual dependency:
dp[2]=2 dp[3]=3
↓ ↓
└────┬───┘
↓
dp[4]=5
Iteration 4: i = 5
━━━━━━━━━━━━━━━━
Calculate dp[5]:
dp[5] = dp[4] + dp[3]
= 5 + 3
= 8
Meaning: To reach step 5, we can:
- Come from step 4 (5 ways) + take 1 step
- Come from step 3 (3 ways) + take 2 steps
Total: 8 ways
dp = [1, 1, 2, 3, 5, 8, 0]
↑
calculated!
Visual dependency:
dp[3]=3 dp[4]=5
↓ ↓
└────┬───┘
↓
dp[5]=8
Iteration 5: i = 6 (FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━
Calculate dp[6]:
dp[6] = dp[5] + dp[4]
= 8 + 5
= 13
Meaning: To reach step 6, we can:
- Come from step 5 (8 ways) + take 1 step
- Come from step 4 (5 ways) + take 2 steps
Total: 13 ways
Final DP table:
dp = [1, 1, 2, 3, 5, 8, 13]
↑
ANSWER!
Visual dependency:
dp[4]=5 dp[5]=8
↓ ↓
└────┬───┘
↓
dp[6]=13
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPLETE DP TABLE VISUALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Index: 0 1 2 3 4 5 6
┌────┬────┬────┬────┬────┬────┬────┐
dp[] │ 1 │ 1 │ 2 │ 3 │ 5 │ 8 │ 13 │
└────┴────┴────┴────┴────┴────┴────┘
↑ ↑ ↑ ↑ ↑ ↑ ↑
base base │ │ │ │ └─ Answer
│ │ │ │
Each value = sum of previous 2 values
Notice: This is the Fibonacci sequence! 🎯
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 13 ways to climb 6 steps! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
📊 State Transition Diagram
dp[i] depends on TWO previous states:
┌──────────────┐
│ dp[i-2] │
│ (2 steps │
│ before) │
└──────┬───────┘
│
├─────────┐
│ │
↓ ↓
┌──────────┐ ┌──────────┐
│ dp[i-1] │ │ dp[i] │
│ (1 step │→ │ (current)│
│ before) │ └──────────┘
└──────────┘
Formula: dp[i] = dp[i-1] + dp[i-2]
Example for dp[4]:
dp[4] = dp[3] + dp[2]
= 3 + 2
= 5 ✓
Each state is built from previous states!
No recursion needed - pure iteration! 🎯
📊 Complexity Analysis
Time Complexity: O(n)
Single loop from 2 to n
Each iteration: O(1) work (just 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)
Better than top-down which has:
- DP table: O(n)
- Recursion stack: O(n)
- Total: O(n) but with larger constant factor
🔵 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 value)
- dp[i-2] (value before previous)
We DON'T need dp[0], dp[1], ..., dp[i-3]!
Example: When calculating dp[6]:
dp[6] = dp[5] + dp[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 = prev1 + prev2
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 climbStairs(int n) {
// Edge cases
if (n <= 1) return 1;
// Instead of array, use two variables
// These represent dp[i-2] and dp[i-1]
int prev2 = 1; // dp[0] - base case
int prev1 = 1; // dp[1] - base case
// Build up from base cases
for (int i = 2; i <= n; i++) {
// Calculate current value
int current = prev1 + prev2;
// ↑ ↑ ↑
// | | └─ dp[i-2]
// | └─ dp[i-1]
// └─ dp[i]
// 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]
return prev1;
}
}
🔍 Detailed Dry Run: n = 5
Input: n = 5
Goal: Find number of ways to climb 5 steps
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Variables (instead of array):
prev2 = 1 (represents dp[0])
prev1 = 1 (represents dp[1])
Visual state:
prev2 prev1
↓ ↓
[1] [1] [?] [?] [?] [?]
0 1 2 3 4 5
We'll calculate positions 2→5 using just these 2 variables!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i = 2
━━━━━━━━━━━━━━━━
Before:
prev2 = 1, prev1 = 1
Calculate current (dp[2]):
current = prev1 + prev2
= 1 + 1
= 2
Shift values:
prev2 = prev1 = 1
prev1 = current = 2
After:
prev2 = 1, prev1 = 2
Visual state:
prev2 prev1
↓ ↓
[1] [1] [2] [?] [?] [?]
0 1 2 3 4 5
Iteration 2: i = 3
━━━━━━━━━━━━━━━━
Before:
prev2 = 1, prev1 = 2
Calculate current (dp[3]):
current = prev1 + prev2
= 2 + 1
= 3
Shift values:
prev2 = prev1 = 2
prev1 = current = 3
After:
prev2 = 2, prev1 = 3
Visual state:
prev2 prev1
↓ ↓
[1] [1] [2] [3] [?] [?]
0 1 2 3 4 5
Iteration 3: i = 4
━━━━━━━━━━━━━━━━
Before:
prev2 = 2, prev1 = 3
Calculate current (dp[4]):
current = prev1 + prev2
= 3 + 2
= 5
Shift values:
prev2 = prev1 = 3
prev1 = current = 5
After:
prev2 = 3, prev1 = 5
Visual state:
prev2 prev1
↓ ↓
[1] [1] [2] [3] [5] [?]
0 1 2 3 4 5
Iteration 4: i = 5 (FINAL)
━━━━━━━━━━━━━━━━━━━━━━━━━
Before:
prev2 = 3, prev1 = 5
Calculate current (dp[5]):
current = prev1 + prev2
= 5 + 3
= 8
Shift values:
prev2 = prev1 = 5
prev1 = current = 8
After:
prev2 = 5, prev1 = 8
Visual state:
prev2 prev1
↓ ↓
[1] [1] [2] [3] [5] [8]
0 1 2 3 4 5
↑
ANSWER!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
VARIABLE EVOLUTION TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i │ prev2 │ prev1 │ current │ Action
───┼───────┼───────┼─────────┼────────────────────
- │ 1 │ 1 │ - │ Initialization
2 │ 1 │ 1 │ 2 │ current=1+1, shift
3 │ 1 │ 2 │ 3 │ current=2+1, shift
4 │ 2 │ 3 │ 5 │ current=3+2, shift
5 │ 3 │ 5 │ 8 │ current=5+3, shift
Final: prev1 = 8
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 8 ways to climb 5 steps! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Space used: Only 3 integer variables!
- prev2
- prev1
- current (temporary)
Compare with bottom-up array: Would need array of size 6!
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=1000000: Saves ~4MB of memory!
🎯 Pattern Recognition - 1D DP
Core Pattern: Fibonacci-like Sequence
Many DP problems follow this pattern:
dp[i] = dp[i-1] + dp[i-2]
Or more generally:
dp[i] = f(dp[i-1], dp[i-2], ...)
Where current state depends on previous 1-2 states.
Examples:
- Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]
- House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- Decode Ways: dp[i] = dp[i-1] + dp[i-2] (with conditions)
Template:
1. Identify base cases
2. Find recurrence relation
3. Build from base to target
4. Optimize space if only need previous k values
How to Identify 1D DP:
✅ State can be represented with single parameter
✅ Current state depends on previous states
✅ No backtracking or exploring multiple paths simultaneously
✅ Optimal substructure exists
✅ Overlapping subproblems
For Climbing Stairs:
✅ State: "at step i"
✅ Depends on: steps i-1 and i-2
✅ Sequential building
✅ Optimal = sum of optimal subproblems
✅ Subproblems repeat (without memoization)
Perfect for 1D DP! 🎯
📝 Quick Revision Notes
🎯 Core Concept
Problem: Count distinct ways to climb n steps, taking 1 or 2 steps at a time.
Key Insight: To reach step n, must come from step (n-1) or step (n-2). So ways(n) = ways(n-1) + ways(n-2) → Fibonacci pattern!
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
public class Solution {
public int climbStairs(int n) {
// // Approach 1 - recursion
// return recursive(n);
// // Approach 2 - top down
// int[] memo = new int[n + 1];
// Arrays.fill(memo, -1);
// return topDown(n, memo);
// // Approach 3 - bottom up
// return bottomUp(n);
// Approach 4 - bottom up space optimized
return bottomUpSO(n);
}
private int bottomUpSO(int n) {
int[] dp = new int[n + 1];
// same base cases
int prev1 = 1;
int prev2 = 1;
dp[0] = prev1;
dp[1] = prev2;
for (int i = 2; i <= n; i++) {
dp[i] = prev2 + prev1;
prev2 = dp[i - 1];
prev1 = dp[i];
}
return dp[n];
}
private int bottomUp(int n) {
int[] dp = new int[n + 1];
// same base cases
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
private int topDown(int n, int[] memo) {
// same base cases
if (n == 0 || n == 1) {
return 1;
}
// memo step added
if (memo[n] != -1) {
return memo[n];
}
return topDown(n - 1, memo) + topDown(n - 2, memo);
}
private int recursive(int n) {
// base cases
if (n == 0 || n == 1) {
return 1;
}
return recursive(n - 1) + recursive(n - 2);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.climbStairs(2)); // 2
System.out.println(s.climbStairs(3)); // 3
System.out.println(s.climbStairs(4)); // 5
System.out.println(s.climbStairs(5)); // 8
System.out.println(s.climbStairs(6)); // 13
}
}
🔑 Key Insights
Base Cases:
dp[0] = 1 (0 steps: already there)
dp[1] = 1 (1 step: one way)
WHY dp[0] = 1?
Mathematical convenience: makes dp[2] = dp[1] + dp[0] = 2 ✓
Logical: "1 way to not move" (do nothing)
Recurrence Relation:
dp[i] = dp[i-1] + dp[i-2]
WHY?
To reach step i, we either:
- Came from step (i-1) and took 1 step
- Came from step (i-2) and took 2 steps
Total ways = sum of both possibilities! 🎯
Space Optimization:
Only need previous 2 values → use 2 variables instead of array!
Pattern:
current = prev1 + prev2
prev2 = prev1
prev1 = current
Reduces O(n) space to O(1)! 🚀
🎪 Memory Aid
"Each step from previous two!"
"Fibonacci in disguise!"
"Bottom-up beats top-down!"
"Two variables, not array!" ✨
⚠️ Common Mistakes
- ❌ Forgetting base case dp[0] = 1
- ❌ Starting loop from i=0 instead of i=2
- ❌ Using dp[i-1] + dp[i-2] before initializing base cases
- ❌ In space-optimized: forgetting to shift variables
- ❌ In top-down: not checking memo before recursing
✅ Interview Talking Points
"This is a classic 1D DP problem with Fibonacci structure.
Approach:
1. Base cases: 0 and 1 steps have 1 way each
2. Recurrence: ways(n) = ways(n-1) + ways(n-2)
3. Build iteratively from base cases
4. Optimize to O(1) space using two variables
Why DP?
- Overlapping subproblems (ways(3) needed multiple times)
- Optimal substructure (optimal answer uses optimal subproblems)
Complexity: O(n) time, O(1) space with optimization"
🎉 Congratulations!
You've mastered the Climbing Stairs problem - the foundation of 1D DP!
What You Learned:
✅ 4 Solution Approaches - Brute Force → Top-Down → Bottom-Up → Space-Optimized
✅ Fibonacci Pattern - Recognizing sequence in DP
✅ Base Case Conversion - From recursion to iteration
✅ State Transitions - How dp[i] depends on previous states
✅ Space Optimization - Reducing O(n) to O(1)
✅ 1D DP Template - Reusable pattern for similar problems
The Beautiful Progression:
Brute Force (O(2^n)):
"Let me try every possible path!"
→ Too slow! Exponential time! 😰
Top-Down (O(n)):
"Let me cache results to avoid recomputation!"
→ Much better! But recursion overhead... 🤔
Bottom-Up (O(n)):
"Let me build iteratively from base cases!"
→ No recursion! Clean and efficient! 😊
Space-Optimized (O(1)):
"I only need last 2 values!"
→ Minimal space! Optimal solution! 🚀⭐
This pattern repeats in MANY DP problems! Master this, master 1D DP! 💪🎯