- 动态规划,
dp[i]
表示爬到i
阶的方法数,爬到i
阶之前必然先爬到i - 1
或i - 2
阶,因此爬到i
阶的方法数就是爬到i - 1
阶和i - 2
阶的方法数之和
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) {
return n;
}
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};