```
/*
1.state f[i] the num to reach no i
2.function f[i] = f[i-1]+ f[i-2]
3.init: f[0] = 1;f[1] = 1;
4.answer:f[n]
time O(n) sapce O(1)
*/
public int climbStairs(int n) {
if (n < 0) return 0;
if (n <= 1) {
return 1;
}
//1.state
int[] dp = new int[n + 1];
//3.init
dp[0] = 1;
dp[1] = 1;
//2 function
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
//4.answer
return dp[n];
}
//time O(n) space O(1)
public int climbStairs2(int n) {
if (n < 0) return 0;
if (n <= 1) {
return 1;
}
int prev1 = 1;
int prev2 = 1;
int res = 0;
for (int i = 2; i <= n; i++) {
res = prev1 + prev2;
prev1 = prev2;
prev2 = res;
}
return res;
}
```