1-D Dynamic Programming Take it or skip it
514. Climbing Stairs
You are at the bottom of a staircase with n steps. Each move takes you up either 1 step or 2 steps, and
you must finish exactly on the top step.
Count the different ways to reach the top. Two ways are different when their lists of moves are different, so 1 then 2 and 2 then 1 are two ways.
The count grows very fast, so return it modulo 109 + 7.
Example 1
Input: n = 4
5Explanation: The five ways are 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 and 2 + 2.
Example 2
Input: n = 1
1Explanation: One step of 1 is the only way.
Example 3
Input: n = 50
365010934Explanation: There are 20,365,011,074 ways. That is more than 109 + 7, and its remainder after dividing by 109 + 7 is 365,010,934.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 105
Clarifying questions
What you would ask an interviewer before writing any code.