Climbing Stairs
Easy · 1-D Dynamic Programming
You are climbing a staircase that has n steps total. Each move you take can advance you either 1 step or 2 steps, and you start at the bottom (step 0). Return the number of distinct sequences of moves that get you exactly to the top. Two sequences count as different if the pattern of 1-step and 2-step moves differs at any point.
Examples
Input: n = 2
Output: 2
Why: You can take two single steps (1+1), or one double step (2).Input: n = 3
Output: 3
Why: Valid move sequences are 1+1+1, 1+2, and 2+1.Input: n = 5
Output: 8
Why: The count follows a Fibonacci-like pattern: 1, 2, 3, 5, 8 for n = 1..5.Constraints
1 <= n <= 45
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Climbing Stairs. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.