Developers

Climbing Stairs

EasyDynamic programmingGrade BAlso known as LeetCode 70

A staircase has n steps. With each move you can climb either 1 step or 2 steps.

Return the number of different sequences of moves that take you exactly to the top.

Examples

Input n = 2
Output 2
Two 1-steps, or one 2-step.
Input n = 3
Output 3
1+1+1, 1+2, or 2+1.
Input n = 5
Output 8

Constraints

  • 1 <= n <= 45

Stuck? Take one hint at a time

Common mistakes
  • Plain recursion without remembering results, which takes exponential time.
  • Getting the starting values wrong (ways(0) = 1, ways(1) = 1).
  • Off by one in the loop, so the answer is for n - 1 or n + 1.
  • Using a table of size n when two variables are enough.
Questions an interviewer may ask next
  • You may also climb 3 steps at a time. What changes in the recurrence?
  • Some steps are broken and cannot be stepped on. Count the ways that avoid them.
  • Return the number of ways modulo 1,000,000,007 for n up to a billion. (Think matrix powers.)
  • Print one valid sequence of moves, not just the count.

How often this is reported

Commonly reported across 9 of 25 tracked companies
9/25

Grade B: Reported in more than one source. This reflects what candidates report, not a guarantee of what any company will ask.