Climbing Stairs
- mosesg1123
- 6 days ago
- 5 min read
Climbing stairs quietly tests whether you recognize overlapping subproblems and know when brute force turns exponential. It’s a perfect warm-up for dynamic programming and a great checkpoint for whether recursion is helping or hurting you.
Problem Statement
You are climbing a staircase with n steps. Each time, you can climb either 1 step or 2 steps.
Return the total number of distinct ways you can reach the top.
Example:
Input: n = 5
Output: 8
Visualization for n = 4:
Step 0 -> 1 -> 2 -> 3 -> 4
Ways:
1-1-1-1
1-1-2
1-2-1
2-1-1
2-2
1. Clarify Requirements Before Jumping Into Code
Let's start by locking down the expectations:
n is a non-negative integer
I can only take steps of size 1 or 2
Order matters, since different sequences count as different ways
This is not asking for the paths themselves, just the count
I also want to confirm whether n = 0 should return 1. Most versions define standing at the top as one valid way.
2. Identify the Category of the Question
This problem exhibits one of the classic signals of a Dynamic Programming problem: Overlapping subproblems. Why? Because counting paths is a classic example of dynamic programming.
Common patterns for this category include:
Top-down recursion with memoization
Bottom-up DP array
Space-optimized DP using rolling variables
3. Consider a Brute-Force Approach to Understand the Problem
Let's imagine that I'm on some step n. What are my options for continuing up the staircase?
Well, I can either:
Take 1 step, or
Take 2 steps
We can flip that to figure out that to get to step n, I have to be at either step n-1 or I can be at step n-2.
If I know all of the possible paths to get to step n-1 and all of the possible paths to get to step n-2, then I can simply add those paths up and I have my solution.
How do I know all the possible paths to get to n-1 and n-2? Well, I keep going backwards until n=1, because I know how many paths there are to get to step n=1: there's just one.
What does this all sound like? It sounds like recursion!
So the total number of paths to reach step n is:
paths(n) = paths(n - 1) + paths(n - 2)But, there's a problem.
I'm doing a lot of recalculations. The time complexity explodes to O(2ⁿ) because of all that extra work, and that quickly becomes unusable even for modest values of n.
It works conceptually, but not practically.
4. Brainstorm More Solutions
So, now that we have a starting point, let's tighten up our solution.
Step 1: Break the problem into smaller subproblems
When solving a Dynamic Programming problem like this one, we want to start by identifying the subproblems that we are trying to solve. We did that in our brute-force recursive solution.
To reach step n, I must come from either:
Step n - 1
Step n - 2
So if I already knew the number of paths to reach those steps, the answer for n is immediate.
That’s the key insight.
Step 2: Look for repeated work
Looking at our recursive solution, we can quickly identify that we are repeating the same calculations: paths(n-1) and paths(n-2) are each being called multiple times for the same inputs.
If we stored the results to those method calls, then we would save substantial amounts of computational power.
In other words, we want to try memoization!
Option 1: Try memoized recursion (Top-Down DP)
I can store the results of each paths(k) calculation so that it is only ever computed once. My recursive solution only has to change one minor way: before I do any calculations, I reference the array for the solution. If I've already calculated paths(k), I can return it immediately from my cache.
This drops the time complexity to O(n) and keeps the recursive structure intact.
While this works, we should also remember recursions key drawback: it adds overhead and stack depth. I may have saved computational power, but stack depth could still be a limiting factor.
Option 2: Flip it into bottom-up DP
Since a top-down DP solution requires recursion, what if we started from the bottom-up instead? It's easy to start: I know there's only 1 path to reach step 0, and I know there's only 1 path to reach step 1 as well. From there I can apply the same calculation we were using in our recursive strategy and store the results in an array.
Paths[0] → 1
Paths[1]→ 1
Paths[2]→ Paths[n-1] + Paths[n-2] = Paths[1] + Paths[0] = 1+1 = 2
Paths[3] → Paths[n-1] + Paths[n-2] = Paths[2] + Paths[1] = 2+1 = 3
…
This solution still has a time complexity of O(n), and we don't have to worry about stack depth as a limiting factor anymore.
Optimize space?
At this point we have a working solution with an optimal time complexity. But what about space complexity? With an array tracking every value of n, our space complexity is O(n).
Can we do better?
To answer that, let's recognize that at any particular moment, we actually only care about two values:
Paths to reach n - 1
Paths to reach n - 2
So what if instead of tracking all possible, we can get an O(1) space complexity by simply tracking these two variables!
5. Discuss Trade-Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Brute-force recursion | O(2ⁿ) | O(n) | Very intuitive | Too slow |
Memoized recursion | O(n) | O(n) | Optimized time complexity | Recursive stack depth issues |
Bottom-up DP array | O(n) | O(n) | Optimized time complexity, easy to reason through | Unnecessary space |
Space-optimized DP | O(n) | O(1) | Optimized, Fast and clean | Slightly less obvious |
6. Write Pseudocode to Structure Your Thoughts
if n <= 1: return 1
prev2 = 1
prev1 = 1
for i from 2 to n:
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
7. Consider Edge Cases
n = 0
n = 1
Very large n
Confirm integer overflow assumptions
Negative inputs (not allowed)
8. Write Full Code Syntax (Java)
public class Solution {
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int prev2 = 1; // ways to reach step 0
int prev1 = 1; // ways to reach step 1
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
9. Test Your Code
System.out.println(new Solution().climbStairs(0)); // 1
System.out.println(new Solution().climbStairs(1)); // 1
System.out.println(new Solution().climbStairs(2)); // 2
System.out.println(new Solution().climbStairs(3)); // 3
System.out.println(new Solution().climbStairs(5)); // 8
10. Key Lessons to Remember for Future Questions
Counting paths is a classic example of a dynamic programming problem
When recursion forces you to recompute the same values, dynamic programming should help you optimize
Many DP problems reduce to simple recurrences
Don't forget to consider space optimization! Space optimization often follows naturally once the recurrence is clear
Comments