n = 0→ 1Doing nothing is the single route to the starting point.
Climbing Stairs
You may climb either one or two steps at a time. Count how many different ordered sequences of moves reach exactly step n. This studio defines n = 0 as one empty sequence.
Know the exact contract
- n is an integer from 0 through 45 in the local coding studio.
- Move order matters: 1 then 2 and 2 then 1 are different routes.
n = 2→ 2The routes are 1 + 1 and 2.
n = 4→ 5The routes are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.
From repeated recursion to two saved counts
Recursively try a one-step move and a two-step move from every position. This mirrors the definition but repeats the same remaining-stair question many times, so its running time grows exponentially.
Let ways(i) be the number of routes to step i. Every final move into i came from i − 1 or i − 2, so ways(i) = ways(i − 1) + ways(i − 2). Start with ways(0) = 1 and ways(1) = 1. Keep only the last two counts while moving upward.
Why it works
Before calculating step i, twoBack equals ways(i − 2) and oneBack equals ways(i − 1). Their sum counts every route to i exactly once, partitioned by whether the final move had length two or one.
Cost
The rolling recurrence visits each step once, using O(n) time and O(1) extra space. The result for n through 45 stays within the exact integer range of JavaScript numbers.
A tempting mistake
Counting only sets of moves loses order. For n = 3, the routes 1+2 and 2+1 are different, so the answer is 3 rather than 2.
What do the last two counts tell us?
Every new route ends with either one step or two steps. Watch those two groups combine.
STEP 1 / 5
ways(0) = 1
At the ground there is one empty sequence of moves.Result: 5
Can you rebuild the recurrence?
This check gives feedback. Only a separate coding pass records an independent solve.
Write the recurrence yourself.
Write solve(n), where n is an integer from 0 through 45. Return the number of ordered routes using one-step and two-step moves. The built-in checks include zero, small values, and fresh larger counts.
Opening the code studio…
A fresh solve is the test.
Loading your saved attempts…
For additional practice, see the related LeetCode challenge.