Back to DSA
Climbing Stairs
easyA staircase has n steps. On each move you may ascend either one step or two steps. Calculate how many distinct sequences of moves will bring you from the ground to the top.
Examples
Example 1:
Input:
n = 4Output:
5Explanation: The five ways are: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2.
Example 2:
Input:
n = 5Output:
8Explanation: There are eight distinct sequences of 1-step and 2-step moves.
Hints
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
}Time complexity
O(n)Space complexity
O(1)