跳转至

70 爬楼梯

https://leetcode.cn/problems/climbing-stairs/description/

爬楼梯和斐波那契数不同之处在于:初始值不同

  • 爬楼梯n == 1, dp[1] = 1; n == 2, dp[2] = 2
  • 斐波那契数n == 0, dp[0] = 0; n == 1, dp[1] = 1; n == 2, dp[2] = 1;

解法一:递归

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

时间复杂度:\(O(2^n)\)

可视为二叉树,树高为n,节点数为\(2^n\),遍历搜索树需要\(2^n\)次

空间复杂度:\(O(n)\)

n个栈空间

解法二:记忆化搜索

class Solution {
private:
    vector<int> m;
    int dfs(int n){
        if(n <= 1)
            return 1;
        int &res = m[n];
        if(res)
            return res;
        return dfs(n - 1) + dfs(n - 2);
    }
public:
    int climbStairs(int n) {
        m.resize(n + 1);
        return dfs(n);
    }
};

时间复杂度:\(O(n)\)

每个状态只会计算一次,共n个状态

空间复杂度:\(O(n)\)

n个栈空间

解法三:动态规划

class Solution {
public:
    vector<int> dp;
    int climbStairs(int n) {
        dp.resize(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};

时间复杂度:\(O(n)\)

状态数n * 状态计算1次

空间复杂度:\(O(n)\)

n个状态

解法四:空间优化

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

时间复杂度:\(O(n)\)

状态数n * 状态计算1次

空间复杂度:\(O(1)\)

只需3个变量