动态规划，每一步都可分为1 + 剩余n-1 + 2 + 剩余n-2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int climbStairs(int n) {
if(n == 1) return 1;
vector<int> dp;
dp.push_back(1);
dp.push_back(2);
for(size_t i = 2; i < n; ++i)
{
dp.push_back(dp[i - 1] + dp[i - 2]);
}
return dp.back();
}
};
|
优化S(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int climbStairs(int n) {
if(n < 2)
return n;
int dp[2]{1, 2};
for(int i = 2; i < n; ++i)
{
dp[0] = dp[0] + dp[1];
swap(dp[0], dp[1]);
}
return dp[1];
}
};
|
review 1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int climbStairs(int n) {
if(n < 2)
return n;
int a = 1, b = 2;
for(int i = 3; i <= n; ++i)
{
a += b;
swap(a, b);
}
return b;
}
};
|