Introduction to the Climbing Stairs Problem
The Climbing Stairs problem is one of the most iconic algorithmic challenges you will encounter in coding interviews and competitive programming. It is a classic dynamic programming problem that appears frequently on platforms like LeetCode, HackerRank, and in technical interviews at major tech companies. Despite its apparent simplicity, the problem elegantly demonstrates fundamental concepts such as recursion, memoization, and iterative optimization.
At its core, the problem asks: given a staircase with n steps, and the ability to climb either 1 or 2 steps at a time, how many distinct ways can you reach the top? The answer reveals a fascinating connection to the Fibonacci sequence and opens the door to understanding more complex dynamic programming patterns.
What Is the Climbing Stairs Problem?
Imagine you are standing at the bottom of a staircase that has n steps. At each move, you can choose to climb either one step or two steps. You need to determine the total number of unique ways to climb from the bottom (step 0) to the top (step n).
For example, if n = 3, the distinct ways are:
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
So the answer is 3. If n = 4, there are 5 distinct ways. If n = 5, there are 8. Notice the pattern: 1, 2, 3, 5, 8 — this is the Fibonacci sequence shifted by one position.
The Mathematical Insight
The key observation is that to reach step n, you must have come from either step n-1 (taking 1 step) or step n-2 (taking 2 steps). Therefore, the total number of ways to reach step n is the sum of the ways to reach step n-1 and step n-2. This gives us the recurrence relation:
ways(n) = ways(n-1) + ways(n-2)
With base cases ways(1) = 1 and ways(2) = 2, this is essentially the Fibonacci sequence.
Why the Climbing Stairs Problem Matters
You might wonder why such a seemingly simple problem deserves so much attention. The answer lies in what it teaches. The Climbing Stairs problem is a microcosm of dynamic programming, and mastering it provides a foundation for solving far more complex problems.
Foundational Dynamic Programming
Dynamic programming is about breaking problems into overlapping subproblems and storing intermediate results to avoid redundant computation. The Climbing Stairs problem is perhaps the cleanest illustration of this principle. Once you understand how to optimize this problem, you can apply the same techniques to problems like the House Robber, Coin Change, and the Knapsack problem.
Interview Relevance
This problem is a favorite among interviewers because it allows them to assess multiple skills in a single question. A candidate might start with a naive recursive solution, then be asked to optimize it with memoization, and finally to reduce space complexity with an iterative approach. This progression reveals the candidate's understanding of time and space complexity trade-offs.
Real-World Applications
While you may not literally count ways to climb stairs in production software, the underlying pattern appears in many real-world scenarios. Route planning, resource allocation, combinatorial counting, and even certain financial modeling problems rely on the same recursive decomposition strategy.
Approach 1: Naive Recursion
The most intuitive solution is to directly translate the recurrence relation into a recursive function. While correct, this approach has exponential time complexity because it recomputes the same subproblems repeatedly.
def climb_stairs_recursive(n):
"""Naive recursive solution - O(2^n) time, O(n) space"""
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)
# Test the function
print(climb_stairs_recursive(5)) # Output: 8
print(climb_stairs_recursive(6)) # Output: 13
This solution works for small values of n, but it becomes impractical for larger inputs. For n = 40, the function may take several seconds or even minutes to complete because the recursion tree grows exponentially.
Approach 2: Recursion with Memoization (Top-Down DP)
To eliminate redundant calculations, we can cache the results of subproblems using a dictionary or Python's functools.lru_cache decorator. This technique, known as memoization, reduces the time complexity from O(2^n) to O(n).
def climb_stairs_memo(n, memo=None):
"""Top-down DP with manual memoization - O(n) time, O(n) space"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
return memo[n]
# Test the function
print(climb_stairs_memo(10)) # Output: 89
print(climb_stairs_memo(45)) # Output: 1836311903
Alternatively, you can use the built-in lru_cache decorator for a cleaner implementation:
from functools import lru_cache
@lru_cache(maxsize=None)
def climb_stairs_cached(n):
"""Top-down DP using lru_cache - O(n) time, O(n) space"""
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
return climb_stairs_cached(n - 1) + climb_stairs_cached(n - 2)
print(climb_stairs_cached(50)) # Output: 20365011074
The lru_cache decorator automatically handles caching for you, making the code more readable and less error-prone. However, be aware that the recursion depth limit in Python (default 1000) may cause issues for very large values of n.
Approach 3: Bottom-Up Dynamic Programming (Tabulation)
The bottom-up approach builds the solution iteratively from the base cases upward. Instead of recursing from the top, we start at step 1 and compute each subsequent step using previously computed values. This eliminates recursion entirely and avoids stack overflow issues.
def climb_stairs_tabulation(n):
"""Bottom-up DP with array - O(n) time, O(n) space"""
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Test the function
print(climb_stairs_tabulation(10)) # Output: 89
print(climb_stairs_tabulation(20)) # Output: 10946
This approach is straightforward and easy to understand. The dp array stores the number of ways to reach each step, and we fill it in order from left to right. The trade-off is that we use O(n) space to store all intermediate results.
Approach 4: Space-Optimized Iterative Solution
Looking closely at the tabulation approach, you will notice that computing dp[i] only requires the values of dp[i-1] and dp[i-2]. We do not need the entire array. By keeping only the last two values, we can reduce the space complexity from O(n) to O(1).
def climb_stairs_optimized(n):
"""Space-optimized iterative solution - O(n) time, O(1) space"""
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
prev2 = 1 # ways to reach step 1
prev1 = 2 # ways to reach step 2
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
# Test the function
print(climb_stairs_optimized(10)) # Output: 89
print(climb_stairs_optimized(100)) # Output: 573147844013817084101
This is the most efficient solution for the standard problem. It runs in linear time and uses constant space. For most practical purposes and interview settings, this is the solution you should aim to produce.
Approach 5: Matrix Exponentiation (Advanced)
For those interested in pushing performance further, there is an advanced technique using matrix exponentiation that solves the problem in O(log n) time. This approach leverages the fact that Fibonacci numbers can be computed by raising a specific transformation matrix to the nth power.
def multiply_matrices(a, b):
"""Multiply two 2x2 matrices"""
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
]
def matrix_power(matrix, n):
"""Raise a 2x2 matrix to the nth power using fast exponentiation"""
result = [[1, 0], [0, 1]] # Identity matrix
base = matrix
while n > 0:
if n % 2 == 1:
result = multiply_matrices(result, base)
base = multiply_matrices(base, base)
n //= 2
return result
def climb_stairs_matrix(n):
"""Matrix exponentiation approach - O(log n) time, O(1) space"""
if n <= 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
# Transformation matrix for Fibonacci
matrix = [[1, 1], [1, 0]]
result = matrix_power(matrix, n - 1)
# The result is in position [0][0] when combined with base case
return result[0][0] + result[0][1]
# Test the function
print(climb_stairs_matrix(10)) # Output: 89
print(climb_stairs_matrix(50)) # Output: 20365011074
While this approach is theoretically faster for very large n, the constant factors and implementation complexity make it overkill for most practical scenarios. It is most useful when n is extremely large (in the millions or beyond) and you need logarithmic time complexity.
Handling Variations of the Problem
Interviewers often modify the Climbing Stairs problem to test your adaptability. Let us explore some common variations and how to handle them.
Variation 1: Variable Step Sizes
Instead of being limited to 1 or 2 steps, suppose you can take any step size from a given set of allowed steps. For example, if allowed steps are [1, 2, 3], you need to count all combinations that sum to n.
def climb_stairs_variable(n, steps):
"""Climbing stairs with variable step sizes - O(n * k) time, O(n) space"""
if n <= 0:
return 0
dp = [0] * (n + 1)
dp[0] = 1 # One way to stay at the ground (do nothing)
for i in range(1, n + 1):
for step in steps:
if i - step >= 0:
dp[i] += dp[i - step]
return dp[n]
# Test with steps [1, 2, 3]
print(climb_stairs_variable(5, [1, 2, 3])) # Output: 13
print(climb_stairs_variable(4, [1, 2])) # Output: 5 (same as original)
Variation 2: Minimum Cost Climbing Stairs
In this variation, each step has an associated cost, and you must find the minimum cost to reach the top. You can start from either step 0 or step 1.
def min_cost_climbing_stairs(cost):
"""Find minimum cost to reach the top - O(n) time, O(1) space"""
n = len(cost)
if n == 0:
return 0
if n == 1:
return cost[0]
prev2 = cost[0]
prev1 = cost[1]
for i in range(2, n):
current = cost[i] + min(prev1, prev2)
prev2 = prev1
prev1 = current
# You can reach the top from either of the last two steps
return min(prev1, prev2)
# Test the function
print(min_cost_climbing_stairs([10, 15, 20])) # Output: 15
print(min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # Output: 6
Variation 3: Counting Distinct Paths with Constraints
Sometimes you may need to avoid certain steps (for example, a broken step that cannot be stepped on). This adds a constraint that modifies the recurrence.
def climb_stairs_with_obstacles(n, broken_steps):
"""Climbing stairs avoiding broken steps - O(n) time, O(n) space"""
broken_set = set(broken_steps)
if n <= 0 or 1 in broken_set:
return 0
dp = [0] * (n + 1)
dp[0] = 1 # Starting position
if 1 not in broken_set:
dp[1] = 1
for i in range(2, n + 1):
if i in broken_set:
dp[i] = 0 # Cannot step here
else:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Test: step 3 is broken
print(climb_stairs_with_obstacles(5, [3])) # Output: 3
Best Practices for Solving Climbing Stairs and Similar Problems
Now that we have explored multiple approaches and variations, let us consolidate the best practices that will help you tackle not just this problem, but any dynamic programming challenge.
Start Simple, Then Optimize
Always begin with the most intuitive solution, even if it is not optimal. The naive recursive approach helps you understand the problem structure and verify your logic. Once you have a working solution, identify the inefficiencies and optimize step by step. This progression demonstrates clear thinking during interviews.
Identify the Recurrence Relation Early
The heart of any dynamic programming problem is the recurrence relation. Before writing any code, spend time understanding how the problem breaks down into subproblems. Ask yourself: "What decisions can I make at each step, and how do those decisions affect the remaining problem?" For Climbing Stairs, the decision is whether to take 1 or 2 steps, and the remaining problem is reaching the top from the new position.
Choose the Right State Representation
Your state representation determines the complexity of your solution. For the basic problem, a single integer n suffices. For variations with obstacles or costs, you may need additional state variables. Keep your state as simple as possible while still capturing all necessary information.
Optimize Space When Possible
After implementing a working DP solution with an array, always check whether you can reduce space usage. If your recurrence only depends on a fixed number of previous values (like the last two in Fibonacci), you can replace the array with a handful of variables. This is a common follow-up question in interviews.
Handle Edge Cases Explicitly
Dynamic programming solutions are prone to off-by-one errors and edge case failures. Always test your solution with edge cases such as n = 0, n = 1, n = 2, and large values of n. Consider negative inputs and empty arrays for variations.
Use Type Hints for Clarity
In production code and even in interviews, adding type hints improves readability and helps catch errors early. Here is how the optimized solution looks with type hints:
def climb_stairs(n: int) -> int:
"""Return the number of distinct ways to climb n stairs.
Args:
n: The total number of stairs to climb.
Returns:
The number of distinct ways to reach the top.
Raises:
ValueError: If n is negative.
"""
if n < 0:
raise ValueError("n must be non-negative")
if n <= 1:
return 1
prev2: int = 1
prev1: int = 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
# Test with various inputs
for i in range(11):
print(f"n={i}: {climb_stairs(i)}")
Write Tests to Validate Your Solution
Always validate your solution with a comprehensive set of test cases. Here is an example using Python's unittest framework:
import unittest
class TestClimbingStairs(unittest.TestCase):
def setUp(self):
self.test_cases = [
(0, 0),
(1, 1),
(2, 2),
(3, 3),
(4, 5),
(5, 8),
(10, 89),
(20, 10946),
(30, 1346269),
]
def test_optimized(self):
for n, expected in self.test_cases:
with self.subTest(n=n):
self.assertEqual(climb_stairs(n), expected)
def test_negative_input(self):
with self.assertRaises(ValueError):
climb_stairs(-1)
if __name__ == "__main__":
unittest.main()
Comparing All Approaches
Let us summarize the different approaches we have covered, along with their time and space complexities, to help you choose the right one for any situation.
- Naive Recursion: O(2^n) time, O(n) space — simple but impractical for large n
- Memoization (Top-Down): O(n) time, O(n) space — intuitive with caching
- Tabulation (Bottom-Up): O(n) time, O(n) space — avoids recursion limits
- Space-Optimized Iterative: O(n) time, O(1) space — best for most scenarios
- Matrix Exponentiation: O(log n) time, O(1) space — best for extremely large n
For interviews and most practical applications, the space-optimized iterative solution is the sweet spot between efficiency and readability. Reserve the matrix exponentiation approach for cases where logarithmic time is genuinely required.
Conclusion
The Climbing Stairs problem is far more than a simple exercise — it is a gateway to understanding dynamic programming. By working through the progression from naive recursion to memoization, tabulation, and finally space optimization, you build a mental framework that applies to countless other problems. The key takeaways are to identify the recurrence relation, choose an appropriate state representation, and optimize iteratively while keeping your code clean and well-tested. Whether you are preparing for interviews or sharpening your algorithmic skills, mastering this problem and its variations will serve you well across your entire programming career.