Asked at

Climbing Stairs

Easy
VerifiedDynamic Programming~15 min

You climb a staircase of n steps. Each move takes 1 or 2 steps. Count the distinct ways to reach the top.

The input arrives as a single number n. Return the count.

Examples

in2
out2

Two ways: 1+1 or 2.

in3
out3

Three ways: 1+1+1, 1+2, 2+1.

Constraints

  • 1 ≤ n ≤ 45
  • Target: O(n) time, O(1) space

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.