Leetcode 70.爬楼梯题解

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入示例

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思路

这是一道非常标准的dp入门题

不如我们先从回溯角度可以写

设n=4 我们可以从反反向跳下去 每次可以跳1或者2格 因此 我们可以得出 (i-1) 和(i-2) 求方案总数

所以最终方程是dfs(i-1)+dfs(i-2)

那么另外一个问题来了 终止条件是什么？

从i-2看到 所以i必须大于2 因为答案不可能是负数

递归代码如下**(Python 和 C++)**

class Solution:
    def climbStairs(self, n: int) -> int:

        def dfs(i):
            if i < 2: return i
            return  dfs(i-1) + dfs(i-2)
        
        return dfs(n+1) # 注意这里加1是因为自己也要算

class Solution {
public:


    int dfs(int n){
        if (n < 2){return n;}
        return dfs(n-1)+dfs(n-2);
    }

    int climbStairs(int n) {
        return dfs(n+1); // 注意这里加1是因为自己也要算
    }
};

你提交之后 会发现 唉？ 超时了

因为递归会造成大量重复计算

从刚才那个例子开始 比如我执行了一次 dfs(n-2) 相当于执行了两次dfs(n-1) 这样会拖慢时间

因此我们可以改成 记忆化搜索 保存计算结果 Python 可以用cache装饰器 c++得自己开数组 代码如下

class Solution:
    def climbStairs(self, n: int) -> int:
        
        @cache
        def dfs(i):
            if i < 2: return i
            return  dfs(i-1) + dfs(i-2)
        
        return dfs(n+1)

class Solution {
public:

    int ans[50];

    int dfs(int n){
        if (n < 2){return n;}
        if(ans[n] != 0){return ans[n];}
        int res = dfs(n-1)+dfs(n-2);
        ans[n] = res;
        return res;
    }

    int climbStairs(int n) {
        for (int i = 0; i < 50; i++){
            ans[i] = 0; // 先把数组初始化
        }
        return dfs(n+1);
    }
};

ok 那我们能不能把递归去掉 把他改成迭代呢？

接下来 我们1:1 把递归翻译成动态方程

dfs(i) = dfs(i-1)+dfs(i-2)
f[i] = f[i-1]+f[i-2]

好 现在边界条件是f[0] = 1 f[1] = 2

写一个从2开始的循环(注意：要循环次数要小于等于n)

以下是代码

// 时间复杂度 : O(n)
// 空间复杂度: O(n)
class Solution {
public:

    int ans[50];

    int climbStairs(int n) {
        if (n==2){return 2;}
        if(n==1){return 1;}
        ans[0] = 1;
        ans[1] = 2;
        for(int i = 2; i < n; i++){
            ans[i] = ans[i-1]+ans[i-2];
        }
        return ans[n-1];
    }
};

# 时间复杂度: O(n)
# 空间复杂度: O(n)
class Solution:
    def climbStairs(self, n: int) -> int:
        
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        dp[1] = 2
        for i in range(2,n+1):
            dp[i] = dp[i-1]+dp[i-2]
        return dp[n-1]

这里又有一个规律

dp[i-1] 是上一个状态 dp[i-2] 是上上个状态

我们能不能用两个变量维持这个状态呢？ 见示例代码

示例代码

# 时间复杂度：O(n)
# 空间复杂度: O(1)
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: return n 
        a = 1
        b = 2
        for i in range(2,n):
            a, b = b, a + b
        return b

// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int climbStairs(int n) {
        if(n<=2){return n;}
        int a = 1, b = 2;
        for(int i = 2; i < n; i++){
            int nxt = b;
            b+=a;
            a = nxt;
        }
        return b;
    }
};

感谢收看