文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Climbing Stairs
2. Solution
f(n) = f(n - 1) + f(n - 2)
O(n)
class Solution {
public:
int climbStairs(int n) {
if(n == 1) {
return 1;
}
int mem[n] = {0};
mem[0] = 1;
mem[1] = 2;
for(int i = 2; i < n; i++) {
mem[i] = mem[i - 1] + mem[i - 2];
}
return mem[n - 1];
}
};
- O(n)
class Solution {
public:
int climbStairs(int n) {
if(n == 1) {
return 1;
}
int first = 1;
int second = 2;
int third = 0;
for(int i = 2; i < n; i++) {
third = first + second;
first = second;
second = third;
}
return second;
}
};
