Climbing Stairs

L8 Hard Dynamic Programming

Concept

The top is reachable only from the two steps below it, so the answer for n is built from the answers for n-1 and n-2 — the Fibonacci pattern.

To reach the top of a stairway with n steps you may climb exactly 1 or 2 steps at a time. Return the number of distinct sequences of climbs that reach the top.

Examples

▸ n = 2

→ 2

▸ n = 3

→ 3

▸ n = 4

→ 5

Progressive Hints

Hint 1 · Nudge

From the top looking down, every step's count is just the sum of the two below it.

Hint 2 · Plan

The number of ways to reach step n equals the ways to reach n - 1 plus the ways to reach n - 2. Build upward from the base cases: 1 way to step 1, 2 ways to step 2.

Hint 3 · Approach

a = 1, b = 2. For steps 3 through n: c = a + b; a = b; b = c. Return b, or 1 when n is 1.

Output

// Run your code to see the output here.