Climbing Stairs
You are at the bottom of a staircase with n steps. Each move climbs either one step or two steps.
Return how many different sequences of moves take you from the bottom (step 0) to exactly the top (step n). Two sequences are different if they differ in at least one move, so climbing 1 + 2 and climbing 2 + 1 count separately.
Constraints
1 <= n <= 45- The answer fits in a 32-bit signed integer.
- The larger tests are too big for a recursion that recomputes the same steps: an exponential solution times out.
Examples
Example 1
Input: n = 2 Output: 2
Two single steps, or one double step.
Example 2
Input: n = 3 Output: 3
1 + 1 + 1, 1 + 2 and 2 + 1. Order matters, so 1 + 2 and 2 + 1 are different climbs.
Example 3
Input: n = 5 Output: 8
The last move lands on step 5 from step 4 (5 ways to get there) or from step 3 (3 ways): 5 + 3 = 8.
JavaScript you'll use: Recursion, the call stack and memoization Arrays: create, read, update
/**
* @param {number} n
* @return {number}
*/
function climbStairs(n) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.