0070. Climbing Stairs
https://leetcode.com/problems/climbing-stairs
Description
You are climbing a staircase. It takes n
steps to reach the top.
Each time you can either climb 1
or 2
steps. In how many distinct ways can you climb to the top?
Example 1:
**Input:** n = 2
**Output:** 2
**Explanation:** There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
**Input:** n = 3
**Output:** 3
**Explanation:** There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
ac
linear DP, maintain 2 variables: prev, curr
class Solution {
public int climbStairs(int n) {
// edge case
if (n <= 1) return n;
int prev = 1;
int curr = 2;
for (int i = 2; i < n; i++) {
int tmp = curr;
curr = curr + prev;
prev = tmp;
}
return curr;
}
}
Last updated
Was this helpful?