You are climbing a staircase with n steps. 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?
Here’s the [Problem Link] to begin with.
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
Constraints:
1 <= n <= 45
Solution 1: Brute Force Approach (Pure Recursion)
Intuition
Think of this like deciding at every step whether to take a small jump (1 step) or a big jump (2 steps)! The most natural way to solve this is to recursively explore all possible combinations of 1-step and 2-step climbs. For the current position at stair index, the number of ways to reach the top is the sum of ways from taking 1 step (to index-1) plus ways from taking 2 steps (to index-2). It’s like asking “From here, how many ways if I take 1 step? How many if I take 2 steps?” and adding them up. This continues until you reach the bottom (0 or 1 stair left, which have obvious solutions).
Detailed Approach
- Base Cases: If index == 0 (no stairs left), there’s 1 way (do nothing). If index == 1, there’s 1 way (take one step).
- Recursive Case: For index ≥ 2, return func(index-1) + func(index-2).
- Direct Implementation: Translate the decision process directly into recursive code.
- No Optimization: Make fresh recursive calls every time, even for overlapping subproblems.
- Tree Structure: Creates a binary tree of recursive calls with lots of redundancy (e.g., func(2) calculated multiple times).
Code
class Solution:
def func(self, index):
# Base cases: 1 way for 0 or 1 stair
if index == 0 or index == 1:
return 1
# Recursive case: ways = ways from (index-1) + ways from (index-2)
return self.func(index - 1) + self.func(index - 2)
def climbStairs(self, n: int) -> int:
return self.func(n)Code Explanation
This solution directly models the climbing choices with recursion. The func handles base cases where 0 stairs have 1 way (you’re already at the top) and 1 stair has 1 way (must take one step). For any other index, it recursively calculates the ways by considering a 1-step climb (func(index-1)) and a 2-step climb (func(index-2)), then adds them. The main function climbStairs starts the recursion from n. This creates a binary tree of calls, where each node represents a decision point.
Dry Run
Let’s trace through: n = 4
func(4):
- Not 0 or 1, so return func(3) + func(2)
func(3):
- Not 0 or 1, so return func(2) + func(1)
func(2):- Not 0 or 1, so return func(1) + func(0)
func(1): ==1, return 1
func(0): ==0, return 1 - func(2) = 1 + 1 = 2
func(1): ==1, return 1
- Not 0 or 1, so return func(1) + func(0)
- func(3) = 2 + 1 = 3
func(2): (calculated again!)
- Not 0 or 1, so return func(1) + func(0)
func(1): ==1, return 1
func(0): ==0, return 1 - func(2) = 1 + 1 = 2
Final: func(4) = 3 + 2 = 5
Notice: func(2), func(1), func(0) are recalculated multiple times!
Time and Space Complexity
- Time Complexity: O(2^n) – Each call branches into 2 more calls, leading to exponential growth
- Space Complexity: O(n) – Maximum depth of recursion stack equals n
Simplifying It
This approach is like exploring every possible path up the stairs by actually walking them all, but forgetting paths you’ve already walked, so you end up walking the same lower sections of stairs over and over again! Very intuitive but extremely inefficient for large n.
Solution 2: Memoization Approach (Top-Down Dynamic Programming)
Intuition
What if we remembered the number of ways to climb each subsection of stairs so we don’t have to recalculate them? Memoization adds a “memory” layer to our recursive approach by storing the results of subproblems in an array. When we need the ways for a particular index, we first check if we’ve already computed it – if yes, just return the stored value. It’s like having a notebook where you write down “Number of ways from stair 3: 3” and look it up next time instead of re-exploring.
Detailed Approach
- Create Memoization Array: Initialize dp array of size n+1 with -1 (uncomputed).
- Check Cache First: In func, if dp[index] != -1, return cached value.
- Compute and Store: If not cached, compute recursively and store in dp[index].
- Same Recursive Structure: Maintain the choice-based recursion but add caching.
- One-Time Computation: Each subproblem (ways for each index) is solved exactly once.
Code
class Solution:
def func(self, index, dp):
# Base cases: 1 way for 0 or 1 stair
if index == 0 or index == 1:
return 1
# Check if already computed
if dp[index] != -1:
return dp[index] # Return cached result
# Compute and store
dp[index] = self.func(index - 1, dp) + self.func(index - 2, dp)
return dp[index]
def climbStairs(self, n: int) -> int:
# Initialize memoization array
dp = [-1] * (n + 1)
return self.func(n, dp)Code Explanation
This solution enhances the recursive approach with memoization. The dp array serves as our cache, starting with -1 for uncomputed states. Before recursing, we check if dp[index] != -1 – if true, return the stored ways immediately. If not, compute by recursing on index-1 and index-2, store the sum in dp[index], and return it. This turns exponential time into linear by ensuring each index’s ways are calculated once and reused.
Dry Run
Let’s trace through: n = 4
Initial: dp = [-1, -1, -1, -1, -1]
func(4, dp):
- index=4 >1 and dp=-1, so compute
- dp = func(3, dp) + func(2, dp)
func(3, dp):
- index=3 >1 and dp=-1, so compute
- dp = func(2, dp) + func(1, dp)
func(2, dp):
- index=2 >1 and dp=-1, so compute
- dp = func(1, dp) + func(0, dp)
func(1, dp): ==1, return 1
func(0, dp): ==0, return 1 - dp = 1 + 1 = 2, dp = [-1, -1, 2, -1, -1]
func(1, dp): ==1, return 1
- dp = 2 + 1 = 3, dp = [-1, -1, 2, 3, -1]
func(2, dp): (called again from func(4))
- dp = 2 != -1, return cached 2 (no recompute!)
Final: dp = 3 + 2 = 5, dp = [-1, -1, 2, 3, 5]
Time and Space Complexity
- Time Complexity: O(n) – Each index from 0 to n is computed exactly once
- Space Complexity: O(n) – dp array of size n+1 plus O(n) recursion stack
Simplifying It
This approach is like exploring the stairs but keeping a notebook of “ways from here” at each landing. The first time you figure out the ways from stair 3, you note it down. Next time you reach stair 3 from another path, you just read your note instead of re-exploring!
Solution 3: Tabulation Approach (Bottom-Up Dynamic Programming)
Intuition
Instead of starting from the top of the stairs and working down, let’s start from the bottom and build up! Tabulation fills an array from the base cases (0 and 1 stair) upwards to n, where the ways to reach each stair i is the sum of ways to reach i-1 and i-2. It’s like counting the ways step by step, building on what you already know from lower stairs.
Detailed Approach
- Initialize DP Array: Create dp of size n+1, set dp = 1, dp = 1.
- Bottom-Up Filling: For index from 2 to n, dp[index] = dp[index-1] + dp[index-2].
- Sequential Order: Ensure dependencies (lower indices) are computed first.
- No Recursion: Pure loop-based approach avoids stack overhead.
- Direct Access: Final answer is simply dp[n].
Code
class Solution:
def climbStairs(self, n: int) -> int:
# Initialize DP array
dp = [-1] * (n + 1)
dp[0] = 1 # 1 way for 0 stairs
dp[1] = 1 # 1 way for 1 stair
# Fill array bottom-up
for index in range(2, n + 1):
dp[index] = dp[index - 1] + dp[index - 2] # Ways = from (index-1) + from (index-2)
return dp[n]Code Explanation
This solution uses iteration to build the solution from base cases up. We set dp = 1 (one way to stay at ground) and dp = 1 (one way to climb one stair). The loop computes each dp[index] using the previously filled values, modeling the choice of coming from 1 step below or 2 steps below. This eliminates recursion and directly computes the answer in linear time.
Dry Run
Let’s trace through: n = 5
Initial: dp = [1, 1, ?, ?, ?, ?]
index = 2:
index = 3:
index = 4:
- dp = dp + dp = 3 + 2 = 5
- dp = [1, 1, 2, 3, 5, ?]
index = 5:
- dp = dp + dp = 5 + 3 = 8
- **dp = [1, 1, 2,
Return dp = 8
Time and Space Complexity
- Time Complexity: O(n) – Single loop from 2 to n, O(1) per iteration
- Space Complexity: O(n) – dp array of size n+1
Simplifying It
This approach is like building a map of the stairs where you note the number of ways to reach each landing, starting from the ground floor. For each higher landing, you just add the ways from the landing directly below and two below – very organized!
Solution 4: Space-Optimized Tabulation (Optimal Approach)
Intuition
Do we really need to store ways for ALL stairs from 0 to n? No – to compute ways for the next stair, we only need the ways for the previous two! Use two variables to track these, updating them as we “climb.” It’s like only remembering the ways to the last two landings you’ve reached.
Detailed Approach
- Initialize Variables: prev2 = 1 (ways for 0), prev = 1 (ways for 1).
- Sliding Window: For each from 2 to n, curr = prev + prev2.
- Update: prev2 = prev, prev = curr (slide the window up).
- Constant Space: Only 3 variables needed.
- Handle Small n: Implicitly covered, but loop starts from 2.
Code
class Solution:
def climbStairs(self, n: int) -> int:
# Base cases implicitly handled by initialization
if n <= 1:
return 1
# Initialize previous two ways
prev2 = 1 # Ways for 0 stairs
prev = 1 # Ways for 1 stair
# Compute ways up to n
for _ in range(2, n + 1):
curr = prev + prev2 # Ways for current = prev + prev2
prev2 = prev # Slide: prev2 becomes prev
prev = curr # Slide: prev becomes curr
return prev # prev now holds ways for nCode Explanation
This optimal solution tracks only the last two ways values. Start with prev2=1 (0 stairs) and prev=1 (1 stair). For each higher stair, compute curr as sum of prev and prev2, then update prev2 to prev and prev to curr. This maintains the two most recent ways values. After the loop, prev equals the ways for n. This achieves O(n) time with O(1) space.
Dry Run
Let’s trace through: n = 5
Initial: prev2 = 1 (0 stairs), prev = 1 (1 stair)
i = 2:
- curr = prev + prev2 = 1 + 1 = 2 (2 stairs)
- prev2 = prev = 1, prev = curr = 2
- State: prev2=1 (1 stair), prev=2 (2 stairs)
i = 3:
- curr = prev + prev2 = 2 + 1 = 3 (3 stairs)
- prev2 = prev = 2, prev = curr = 3
- State: prev2=2 (2 stairs), prev=3 (3 stairs)
i = 4:
- curr = prev + prev2 = 3 + 2 = 5 (4 stairs)
- prev2 = prev = 3, prev = curr = 5
- State: prev2=3 (3 stairs), prev=5 (4 stairs)
i = 5:
- curr = prev + prev2 = 5 + 3 = 8 (5 stairs)
- prev2 = prev = 5, prev = curr = 8
- State: prev2=5 (4 stairs), prev=8 (5 stairs)
Return prev = 8
Time and Space Complexity
- Time Complexity: O(n) – Single loop from 2 to n, O(1) per iteration
- Space Complexity: O(1) – Only a few variables used
Simplifying It
This approach is like climbing the stairs while only remembering how many ways you could have reached the last two steps. As you take each new step, you update your memory with the new total, forgetting older info since you don’t need it anymore!
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Recursion (Brute Force) | O(2^n) | O(n) | Easy | Understanding the concept |
| Memoization (Top-Down DP) | O(n) | O(n) | Medium | Learning DP concepts |
| Tabulation (Bottom-Up DP) | O(n) | O(n) | Medium | Systematic DP approach |
| Space-Optimized Tabulation | O(n) | O(1) | Medium-Hard | Production code |
The space-optimized tabulation is the best for efficiency, with optimal time and minimal space. Each approach builds on the last, showing DP evolution: from wasteful recursion to cached recursion, to iterative building, to ultra-efficient variable tracking. Note that this problem is mathematically equivalent to the Fibonacci sequence, shifted by one index!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
