Climbing Stairs
Problem
Given an integer n representing the number of steps, return the number of distinct ways to climb to the top, where each time you can either climb 1 or 2 steps.
- 1 ≤ n ≤ 45
Example
n = 33The possible ways to climb 3 steps are: (1 step + 1 step + 1 step), (1 step + 2 steps), and (2 steps + 1 step). The algorithm uses recursion with memoization to count these combinations efficiently. Starting from step 3, it breaks down the problem into counting ways to reach steps 2 and 1, which are computed recursively and cached to avoid redundant calculations.
Approach
Straightforward Solution
A naive recursive solution explores all possible sequences of 1-step and 2-step moves, leading to exponential time complexity due to repeated calculations of the same subproblems.
Core Observation
The number of ways to reach step i depends solely on the ways to reach steps i-1 and i-2, reflecting the problem's optimal substructure and overlapping subproblems.
Path to Optimal
Recognizing the overlapping subproblems, memoization is introduced to cache results of subproblems, transforming the exponential recursion into a linear time dynamic programming solution. This approach stores the number of ways to reach each step, avoiding redundant computations.
Optimal Approach
PreviewImplement a top-down recursive function with memoization that returns the number of ways to reach step i by summing the ways to reach steps i-1 and i-2…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each state i from 0 to n is computed once and stored in the memo dictionary, preventing repeated calculations and resulting in linear time complexity.
Space
O(n)
The memo dictionary stores results for each step up to n, and the recursion stack can go as deep as n, leading to O(n) auxiliary space usage.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem's solution depends on overlapping subproblems with optimal substructure, use recursion with memoization to cache intermediate results and avoid redundant computations, converting exponential recursion into efficient linear time.
Solution
| 1 | class Solution:
|
| 2 | def climbStairs(self, n: int) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i):
|
| 6 | if i <= 1:
|
| 7 | return 1
|
| 8 | if i in memo:
|
| 9 | return memo[i]
|
| 10 |
|
| 11 | memo[i] = dp(i - 1) + dp(i - 2)
|
| 12 | return memo[i]
|
| 13 |
|
| 14 | return dp(n) |
Step-by-Step Solution
Implement Memoized Recursive Function to Count Ways
| 3 | memo = {}
|
| 5 | def dp(i):
|
| 6 | if i <= 1:
|
| 7 | return 1
|
| 8 | if i in memo:
|
| 9 | return memo[i]
|
| 11 | memo[i] = dp(i - 1) + dp(i - 2)
|
| 12 | return memo[i]
|
Objective
To define a recursive function that computes the number of ways to reach step i, using memoization to cache and reuse results.
Key Insight
The problem breaks down into counting ways to reach the previous two steps, reflecting the Fibonacci sequence structure. Memoization ensures that once the number of ways to reach a step is computed, it is stored and reused, preventing exponential recomputation and enabling efficient top-down dynamic programming.
Interview Quick-Check
Core Logic
The recursive function returns 1 for base cases (i <= 1) and otherwise sums the results of dp(i-1) and dp(i-2), caching results in memo to avoid redundant calls.
State & Boundaries
Base cases handle steps 0 and 1, returning 1 as there is exactly one way to stand still or take a single step.
Common Pitfalls & Bugs
Forgetting to check the memo before recursion leads to exponential time due to repeated subproblem evaluations.
Complexity
Memoization reduces the time complexity from O(2^n) to O(n) by ensuring each subproblem is solved once.
Return the Total Number of Ways to Climb n Steps
To initiate the recursive computation for the full problem and return the final result.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if i in memo:Check if the result for step i is already cached in memo.
This lookup prevents recomputation of subproblems, which is the key optimization that reduces time complexity from exponential to linear.
memo[i] = dp(i - 1) + dp(i - 2)Compute the number of ways to reach step i by summing ways to reach steps i-1 and i-2.
This recurrence captures the problem's optimal substructure, reflecting that each step can be reached from the two preceding steps, forming the Fibonacci-like relation.
if i <= 1:Return 1 if i is 0 or 1, representing base cases.
These base cases define the minimal steps scenarios where there is exactly one way to climb, serving as the foundation for the recursion.
Full line-by-line criticality + rationale for all 9 lines available on Pro.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to linear in this problem?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Climbing Stairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Climbing Stairs drill