March 24
Climbing Stairs
How to notice the recurrence from the last two choices and use that as an entry point to dynamic programming.
Dynamic Programming Beginner 15 min TypeScript
You are climbing a staircase. To reach the top with n steps, you can climb 1 or 2 steps at a time.
Return how many distinct ways there are to reach the top.
Example:
Input: n = 3
Output: 3
The ways are: 1+1+1, 1+2, 2+1.
What to notice before coding
- The problem asks for the number of ways, not the minimum number of moves.
- To reach the current step, the last jump can only be 1 or 2.
- The same subproblems repeat if you use pure recursion.
Common mistakes
- confusing the problem with minimizing steps
- getting the base cases wrong for `n = 1` and `n = 2`
Step 1 — Ask where the last move could have come from
To reach step n, the last move can only be:
- from
n - 1ton - from
n - 2ton
There is no third option.
That already suggests that the number of ways to reach n depends on the two previous cases.
Step 2 — Write the recursive baseline
The first correct idea is usually:
export function climbStairs(n: number): number {
if (n <= 2) {
return n
}
return climbStairs(n - 1) + climbStairs(n - 2)
}
It works. But it repeats a lot of work.
To calculate climbStairs(5), for example, you recalculate climbStairs(3) more than once.
Step 3 — Identify the recurrence
The core relationship is:
ways(n) = ways(n - 1) + ways(n - 2)
Because every path to n must end from one of those two previous steps.
Step 4 — Store only what really matters
You do not need the whole recursion tree.
You only need to know:
- how many ways reach the previous step
- how many ways reach two steps before
Everything else can be discarded as you move forward.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function climbStairs(n: number): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 — Pure recursion before memoization
Good for seeing the idea, bad for scaling.
export function climbStairs(n: number): number {
if (n <= 2) {
return n
}
return climbStairs(n - 1) + climbStairs(n - 2)
}The problem is not the formula. It is the repeated work.
Solution 2 — dynamic programming with reduced state in O(1) space
Now the same recurrence runs iteratively.
export function climbStairs(n: number): number {
if (n <= 2) {
return n
}
let twoStepsBefore = 1
let oneStepBefore = 2
for (let stair = 3; stair <= n; stair += 1) {
const current = oneStepBefore + twoStepsBefore
twoStepsBefore = oneStepBefore
oneStepBefore = current
}
return oneStepBefore
}You keep only the state needed to compute the next step.
What to say in the interview
A strong short explanation would be:
To reach step
n, the last move can only come fromn - 1orn - 2. That gives the recurrencef(n) = f(n - 1) + f(n - 2). Pure recursion works, but it recalculates subproblems. So I turn it into iterative dynamic programming and keep only the previous two states.
That shows that you:
- found the right recurrence
- explained why pure recursion wastes work
- connected dynamic programming to a concrete need
When this pattern shows up again
The same pattern comes back when you need to:
- count ways to reach a state
- build an answer from a few previous states
- replace repetitive recursion with linear dynamic programming
- recognize repeated subproblems early
The point is not memorizing “this looks like Fibonacci.”
The point is justifying where the recurrence comes from.