EasyDpAI interview only
Climbing Stairs Order Does Not Matter
Asked atamazonmicrosoftadobe
01 · Problem
You need to climb a staircase of n steps, moving either 1 or 2 steps at a time. Unlike the classic version, the order of moves does not matter: two climbs that use the same number of 1-steps and the same number of 2-steps count as the same way (for example 1+2 and 2+1 are one way).
Return the number of distinct ways to reach exactly step n.
02 · Examples
Example 01
Input
n = 4
Output
3
The distinct combinations are {1,1,1,1}, {1,1,2} and {2,2}.
Example 02
Input
n = 5
Output
3
The distinct combinations are {1,1,1,1,1}, {1,1,1,2} and {1,2,2}.
Example 03
Input
n = 1
Output
1
The only option is a single 1-step.
03 · Constraints
- 011 <= n <= 104
- 02Each move climbs exactly 1 or 2 steps
- 03The answer fits in a 32-bit signed integer
04 · Optimal complexity
- Time
- O(1)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.