Climbing Stairs
Easy1-D dynamic programming
A staircase has n steps. Each move climbs either 1 step or 2 steps.
Return how many different sequences of moves take you from the bottom to the top.
Examples
Input: n = 3 Output: 3
1+1+1, 1+2 and 2+1.
Input: n = 4 Output: 5
1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Constraints
1 ≤ n ≤ 45
Stuck?
Hint 1
Your last move was either 1 step or 2. So the ways to reach step n are the ways to reach n - 1 plus the ways to reach n - 2.
Hint 2
Plain recursion repeats the same work and runs out of time long before n = 45. Keep only the last two counts as you climb.
The idea
Your last move onto step n is either 1 step, from n - 1, or 2 steps, from n - 2. So the ways to reach n are the ways to reach n - 1 plus the ways to reach n - 2, which is the Fibonacci sequence. Build the counts up from the bottom, keeping only the last two.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
There is one way to stand at the bottom, step 0, and one way to reach step 1. Those two counts start the sequence.
function climbStairs(n) { let previous = 1; let current = 1; for (let step = 2; step <= n; step++) { const next = previous + current; previous = current; current = next; } return current;}The trap
The loop is right, so b ends on the count for step n, but it returns a, the count for step n - 1. When n is 1 both are 1, so that case passes. From n = 2 on, every answer is the previous step's count.
function climbStairs(n) { let a = 1, b = 1; for (let i = 1; i < n; i++) [a, b] = [b, a + b]; return a; // one step behind}