easyDynamic Programming 1DPure DSA~11 min
Deploy Step Ways
A staged rollout advances either one stage or two stages at a time. Count the distinct ways to go from stage 0 to the final stage n.
Problem
You are climbing a staircase with n steps. Each move you may climb 1 or 2 steps. Return the number of distinct ways to reach the top.
Input
An integer n (1 ≤ n ≤ 45).
Output
An integer — the number of distinct ways.
Constraints
- Each move is exactly 1 or 2 steps
- Result fits in a 32-bit signed integer for n ≤ 45
Examples
Example 1
Input
n = 2
Output
2
1+1 or 2.
Example 2
Input
n = 3
Output
3
1+1+1, 1+2, or 2+1.