You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1
Input: n = 3
Output: 3
Explanation: Three ways: 1+1+1, 1+2, 2+1.
1 <= n <= 45State the recurrence out loud before coding: to reach step n, your last move was either a 1-step from n-1, or a 2-step from n-2 — so ways(n) = ways(n-1) + ways(n-2).
This is structurally identical to the Fibonacci sequence — recognizing that connection is the whole insight.
You don't need an array to hold every intermediate value — only the last two values are ever needed at once.
public int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2; // ways(1)=1, ways(2)=2
for (int i = 3; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Time: O(n) · Space: O(1)