The fastest solution leverages state transition dynamic programming by recognizing that the number of ways to reach step n equals the sum of ways to reach steps n-1 and n-2. GhostInterview guides you through memoization to avoid recomputation and illustrates iterative DP for optimal space. Understanding the transition formula f(n) = f(n-1) + f(n-2) ensures precise, efficient solutions without redundant calculations.
Problem Statement
You are given a staircase with n steps, and you can climb either 1 or 2 steps at a time. Determine how many distinct sequences of steps will take you to the top, emphasizing the dynamic programming pattern where each state depends on previous states.
For example, given n = 3, the possible ways to climb are [1,1,1], [1,2], and [2,1]. Constraints require 1 <= n <= 45, and you should focus on leveraging memoization or iterative DP to compute results efficiently.
Examples
Example 1
Input: n = 2
Output: 2
There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Example 2
Input: n = 3
Output: 3
There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
Constraints
- 1 <= n <= 45
Solution Approach
Recursive with Memoization
Define a helper function that returns the number of ways to reach step k. Use memoization to store results for each step to avoid redundant recursion. Base cases are step 0 and step 1. The transition is f(k) = f(k-1) + f(k-2), directly reflecting the allowed step sizes.
Iterative Dynamic Programming
Use a DP array dp[0..n] where dp[i] stores the number of ways to reach step i. Initialize dp[0] = 1, dp[1] = 1. Iteratively fill dp[i] = dp[i-1] + dp[i-2]. This approach avoids recursion overhead and is simple to implement for the state transition pattern.
Optimized Space Using Two Variables
Instead of an array, keep only two variables representing previous two steps. Update iteratively using temp = prev1 + prev2. This reduces space complexity to O(1) while still adhering to the same transition f(n) = f(n-1) + f(n-2).
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) for iterative or memoized DP, since each step is computed once. Space complexity is O(n) for the DP array or memoization table, reducible to O(1) with two-variable optimization. The recurrence ensures linear growth without recomputation.
What Interviewers Usually Probe
- Asks for the number of ways to reach step n using allowed steps.
- Hints at using previous step results, indicating dynamic programming pattern recognition.
- Tests understanding of optimizing space from DP array to constant variables.
Common Pitfalls or Variants
Common pitfalls
- Attempting plain recursion without memoization leads to exponential time complexity.
- Confusing step sequences, double-counting combinations instead of counting distinct paths.
- Ignoring base cases or incorrectly initializing dp array, causing off-by-one errors.
Follow-up variants
- Changing allowed steps to 1, 2, or 3 alters the state transition and requires adjusting the DP recurrence.
- Finding minimum steps to reach the top instead of counting distinct ways changes the problem to a min-path DP variant.
- Adding constraints like broken steps introduces conditional checks in the transition formula.
How GhostInterview Helps
- Provides step-by-step guidance to apply memoization and iterative DP without wasting time on brute-force recursion.
- Highlights base cases and transition formulas to ensure solutions respect the state transition pattern.
- Offers visualization of step sequences to verify correctness and spot common off-by-one errors.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the recurrence relation for Climbing Stairs?
The number of ways to reach step n is f(n) = f(n-1) + f(n-2), reflecting the allowed step sizes of 1 or 2.
Can Climbing Stairs be solved using pure recursion?
Yes, but without memoization, recursion has exponential time complexity and will fail for larger n.
How can I reduce space in the DP solution?
Keep only the last two computed values and update iteratively to reduce space from O(n) to O(1).
What is the time complexity of iterative DP for Climbing Stairs?
Iterative DP runs in O(n) time since each step is calculated exactly once using previous results.
How does the problem exemplify state transition dynamic programming?
Each step depends on previous states, making f(n) a direct sum of f(n-1) and f(n-2), the core state transition pattern.
Need direct help with Climbing Stairs instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Climbing Stairs from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Different Ways to Add Parentheses by splitting on each operator and memoizing every subexpression result list.
Open problem page#464 Can I WinDetermine if the first player can guarantee a win in a turn-based number selection game using state transition dynamic programming.
Open problem page#509 Fibonacci NumberCalculate the nth Fibonacci number using state transition dynamic programming and recursive techniques efficiently in interviews.
Open problem page