126. Climbing Stairs
Start on the ground and reach exactly step n using moves of one or two steps. Count all different ordered sequences of moves that reach the top.
Taking one step then two differs from taking two then one. There is one empty sequence for a staircase with zero steps.
Example 1
Input
n=0
Output
1
Explanation: The empty path is a complete path; returning zero would erase a necessary counting identity.
Example 2
Input
n=3
Output
3
Explanation: The ordered paths are [1,1,1], [1,2], and [2,1].
Example 3
Input
n=5
Output
8
Explanation: A final one-step can extend any of five paths to 4; a final two-step can extend any of three paths to 3.
Example 4
Input
n=91
Output
7540113804746346429
Explanation: This is F(92), the largest supported staircase count that fits a signed long. F(93), needed for n=92, does not fit.
Constraints
0 <= n <= 91
Hints
Hint 1
Group all valid sequences by their last move. Which smaller heights remain?
Hint 2
Give the empty sequence a count and write a state sentence before the recurrence.
Hint 3
Keep W(s−2) and W(s−1); compute their sum before moving the two-register frontier.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Five steps: preserve both predecessors
5
8