Climbing Stairs

Easy#701d array

A staircase has n steps. Each move takes you up 1 or 2 steps. In how many different orders of moves can you get from the ground to the top step? Our example: n = 6 — there are 13 ways.

70 Climbing StairsWalkthrough · 1×

Example: n = 6. On top is the staircase, under it the table ways: how many climbs end on each step.

stepsways0123456
this stepfilledread fromanswer

An empty table: one cell for the ground (step 0) and one for each of the 6 steps

01/24
restart · back · play · step
Speed
1function climbStairs(n):
2 ways = new array of size n + 1
3 ways[0] = 1 // the ground: no moves, one way
4 ways[1] = 1
5 for i from 2 to n:
6 one = ways[i - 1] // last move is 1 step
7 two = ways[i - 2] // last move is 2 steps
8 ways[i] = one + two
9 return ways[n]
state
ways
[–, –, –, –, –, –, –]
i
–
one
–
two
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every climb to step i ends with exactly one last move: a 1-step from i − 1 or a 2-step from i − 2. So the climbs split into two groups with nothing in common, and ways[i] = ways[i − 1] + ways[i − 2].
  2. ways[0] = 1 is the empty climb before any move. A 2-step from the ground to step 2 extends it, so step 2 gets 1 + 1 = 2 ways, not 1.
  3. Each cell reads only the two cells before it, which are already filled, so one pass from left to right is enough. Brute force lists every climb one by one, and their number grows exponentially, as fast as the numbers in the cells.

Complexity

Time O(n): each step is filled once with one addition. Memory O(n) for the table; two variables for the last two cells are enough, which gives O(1).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.