easyDynamic programming, 1DRecursion target 15 min
Climbing stairs
A staircase has n steps. Each stride takes you up 1 step or 2 steps, and no stride may go past step n. A climb is the list of strides you take, in order, from the floor to step n. Order matters: [1, 2] and [2, 1] are two different climbs of 3 steps.
Return the number of different climbs.
Example 1
Input
n = 4Output5The five climbs are [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1] and [2, 2].
Example 2
Input
n = 1Output1One stride of 1. A stride of 2 would go past the top.
Example 3
Input
n = 5Output8A climb of 5 ends with a 1 (from step 4, which 5 climbs reach) or a 2 (from step 3, which 3 climbs reach). 5 + 3 = 8.
Constraints
1 ≤ n ≤ 45
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.