easy

Climbing Stairs

You climb a staircase of n steps, taking either one or two steps at a time. Count the number of distinct ways to reach the top.

Constraints

1 ≤ n ≤ 45

Examples

in: n = 3

out: 3

1+1+1, 1+2, 2+1.

Recognition clues

"Number of ways" to reach a state
The last move came from step n−1 or n−2
Overlapping subproblems — Fibonacci in disguise

Pattern

Dynamic Programming

Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.

Climbing Stairs Fibonacci Numbers 1D (Linear) DP Tabulation (Bottom-Up DP)

Solution

Let ways(i) be the number of ways to reach step i. The last move was a single step from i - 1 or a double step from i - 2, so ways(i) = ways(i - 1) + ways(i - 2) with ways(0) = ways(1) = 1. Iterate from 2 to n keeping only the last two values.

time O(n)space O(1)

Alternative approaches

Naive recursion is exponential. Matrix exponentiation or Binet's formula gives O(log n) for very large n.

Code it yourself

Solve in

Hints:

Learn Dynamic Programming ▶ Visualize