Climbing stairs

Easy TimeO(2ⁿ) naive, O(n) memoised SpaceO(n)

A staircase has n steps, and each move takes either 1 or 2 of them, nothing else. Return how many distinct ways there are to reach the top — 5 steps give 8. Two climbs are different when the order of their moves differs, so 1 + 2 and 2 + 1 both count. n is at least 1.

Examples

Example 1

Input
n = 5
Output
8
Five 1s; three 1s and a 2 in 4 orders; one 1 and two 2s in 3 orders — 1 + 4 + 3 = 8.

Example 2

Input
n = 1
Output
1
One step, and a single move is the only thing that reaches it.

The Code

function climbStairs(n) {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}
climbStairs(5);
Done
Step through climbStairs(5) call by call

More like this

All dynamic programming examples (20) →