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
Implement 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. The memo dictionary caches intermediate results, ensuring each subproblem is solved once, resulting in O(n) time and space complexity.
Time
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) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int climbStairs(int n) { |
| 6 | Map<Integer, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | return dp(n, memo); |
| 9 | } |
| 10 | |
| 11 | private int dp(int i, Map<Integer, Integer> memo) { |
| 12 | if (i <= 1) { |
| 13 | return 1; |
| 14 | } |
| 15 | if (memo.containsKey(i)) { |
| 16 | return memo.get(i); |
| 17 | } |
| 18 | |
| 19 | int result = dp(i - 1, memo) + dp(i - 2, memo); |
| 20 | memo.put(i, result); |
| 21 | return result; |
| 22 | } |
| 23 | } |
| 1 | #include <unordered_map> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | int climbStairs(int n) { |
| 8 | unordered_map<int, int> memo; |
| 9 | return dp(n, memo); |
| 10 | } |
| 11 | |
| 12 | private: |
| 13 | int dp(int i, unordered_map<int, int>& memo) { |
| 14 | if (i <= 1) { |
| 15 | return 1; |
| 16 | } |
| 17 | auto it = memo.find(i); |
| 18 | if (it != memo.end()) { |
| 19 | return it->second; |
| 20 | } |
| 21 | |
| 22 | int result = dp(i - 1, memo) + dp(i - 2, memo); |
| 23 | memo[i] = result; |
| 24 | return result; |
| 25 | } |
| 26 | }; |
| 1 | var climbStairs = function(n) { |
| 2 | const memo = {}; |
| 3 | |
| 4 | function dp(i) { |
| 5 | if (i <= 1) { |
| 6 | return 1; |
| 7 | } |
| 8 | if (memo.hasOwnProperty(i)) { |
| 9 | return memo[i]; |
| 10 | } |
| 11 | |
| 12 | memo[i] = dp(i - 1) + dp(i - 2); |
| 13 | return memo[i]; |
| 14 | } |
| 15 | |
| 16 | return dp(n); |
| 17 | }; |
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
| 14 | return dp(n) |
Objective
To initiate the recursive computation for the full problem and return the final result.
Key Insight
The final answer is the number of ways to reach step n, obtained by calling the memoized recursive function. This single call triggers the entire top-down dynamic programming process, leveraging cached results for efficiency.
Interview Quick-Check
Core Logic
Calling dp(n) starts the recursion and returns the total number of distinct ways to climb n steps.
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.
return 1Return 1 for base cases where i <= 1.
This line ensures the recursion terminates correctly and provides the correct count for the smallest subproblems, preventing infinite recursion.
return memo[i]Return the cached result for step i if available.
Returning the memoized value immediately avoids unnecessary recursive calls, ensuring efficient reuse of previously computed results.
memo = {}Initialize a dictionary to cache computed results for subproblems.
This memo dictionary is essential for storing intermediate results, enabling the algorithm to avoid redundant recursive calls and achieve linear time complexity.
return dp(n)Invoke the recursive function for step n and return the final count.
This call initiates the entire top-down dynamic programming process and returns the total number of distinct ways to climb n steps.
def dp(i):Define the recursive function dp that computes ways to reach step i.
Encapsulating the problem in a recursive function with memoization captures the problem's optimal substructure and overlapping subproblems, forming the basis of the dynamic programming solution.
return memo[i]Return the computed number of ways for step i.
Returning the memoized result completes the recursive call, propagating the computed value up the call stack.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to linear in this problem?
Because memoization caches the results of subproblems, each unique state is computed only once, eliminating redundant recursive calls and thus reducing the overall time complexity to O(n).
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