Learning Outcome
After this lesson, you should be able to turn repeated recursive choices into a simple recurrence with constant memory.
Problem Statement
Given n stairs, return how many distinct ways you can climb to the top when each move can take 1 or 2 steps.
| Input | Output | Why |
|---|---|---|
n = 4 | 5 | The valid ways are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2. |
Brute Force Approach
Try every sequence of 1-step and 2-step moves recursively. This repeats the same subproblems many times.
Optimized Approach
Let ways[n] = ways[n
- 1] + ways[n
- 2]. Keep only the previous two values because each state depends on two earlier states.
Exact Pseudocode
if n <= 2:
return n
one = 1
two = 2
for step from 3 to n:
current = one + two
one = two
two = current
return twoReference Code
class Solution:
def climbStairs(self, n):
if n <= 2:
return n
one, two = 1, 2
for step in range(3, n + 1):
current = one + two
one = two
two = current
return twoSample Dry Run
| Step | State | Result |
|---|---|---|
| Base | ways(1)=1, ways(2)=2 | one=1, two=2 |
| Step 3 | current = 1 + 2 | ways(3)=3 |
| Step 4 | current = 2 + 3 | ways(4)=5 |
| Return | two = 5 | answer = 5 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | The loop computes each stair count once. |
| Space | O(1) | Only two rolling values are stored. |
Edge Cases
- n = 1 and n = 2 are base cases.
- Starting the loop at the wrong step shifts the answer.
- For very large n, confirm whether modulo is required.
Interview Checklist
- Define the recurrence before writing code.
- Use base cases that match the prompt.
- Update rolling variables in the correct order.
FAQs
Why is this Fibonacci DP?
Each stair can be reached from one step before or two steps before, so the recurrence matches Fibonacci-style growth.
Why not store the full DP array?
You can, but only the previous two states are needed for the next state.
What is the core pattern?
Rolling-state linear DP.