• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int climbStairs(int n) {
// dp[i] := # of distinct ways to climb to i-th stair
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2];

return dp[n];
}
};
``````

## JAVA

``````class Solution {
public int climbStairs(int n) {
// dp[i] := # of distinct ways to climb to i-th stair
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2];

return dp[n];
}
}
``````

## Python

``````class Solution:
def climbStairs(self, n: int) -> int:
# dp[i] := # of distinct ways to climb to i-th stair
dp = [1, 1] + [0] * (n - 1)

for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int climbStairs(int n) {
int prev1 = 1;  // dp[i - 1]
int prev2 = 1;  // dp[i - 2]

for (int i = 2; i <= n; ++i) {
const int dp = prev1 + prev2;
prev2 = prev1;
prev1 = dp;
}

return prev1;
}
};
``````

## JAVA

``````class Solution {
public int climbStairs(int n) {
int prev1 = 1; // dp[i - 1]
int prev2 = 1; // dp[i - 2]

for (int i = 2; i <= n; ++i) {
final int dp = prev1 + prev2;
prev2 = prev1;
prev1 = dp;
}

return prev1;
}
}
``````

## Python

``````class Solution:
def climbStairs(self, n: int) -> int:
prev1 = 1  # dp[i - 1]
prev2 = 1  # dp[i - 2]

for _ in range(2, n + 1):
dp = prev1 + prev2
prev2 = prev1
prev1 = dp

return prev1
``````