学校网站建设报价_深圳政府在线_seo搜索引擎优化人员_佛山网站优化排名推广

70. 爬楼梯 - 力扣（LeetCode）

题目要求：

解法-1 动态规划 O(N)

        这是一道简单的动态规划题，要得到达到第 i 个阶梯的方法总数，就需要得到到达它的上一步 i-1和 i-2 的方法总数，即：dp[i] = dp[i-1]+dp[i-2]。

        使用虚拟位让代码更简洁：

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+2);dp[0] = 0; // 虚拟位初始化dp[1] = 1; // 虚拟位初始化for(int i = 2;i < n+2;i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n+1];}
};

        优化-使用滑动数组减少内存消耗：

class Solution {
public:int climbStairs(int n) {int a = 0;int b = 1;int c;for(int i = 0;i < n;i++){c = a + b;a = b;b = c;}return c;}
};

解法-2 递归 O(N) 会超时

class Solution {
public:int climbStairs(int n) {if(n <= 2)return n;return climbStairs(n-1)+climbStairs(n-2);}
};