70. Climbing Stairs


You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step 

Constraints:

  • 1 <= n <= 45

这篇博客最开始名字叫做爬梯子问题,总是有童鞋向博主反映移动端打不开这篇博客,博主觉得非常奇怪,自己也试了一下,果然打不开。心想着是不是这个博客本身有问题,于是想再开一个相同的帖子,结果还是打不开,真是见了鬼了。于是博主换了个名字,结果居然打开了?!进经过排查后发现,原来是“爬梯子”这三个字是敏感词,放到标题里面,博客就被屏蔽了,我也真是醉了,完全是躺枪好么,无奈之下,只好改名为爬楼梯问题了 -。-|||。

这个爬梯子问题最开始看的时候没搞懂是让干啥的,后来看了别人的分析后,才知道实际上跟斐波那契数列非常相似,假设梯子有n层,那么如何爬到第n层呢,因为每次只能爬1或2步,那么爬到第n层的方法要么是从第 n-1 层一步上来的,要不就是从 n-2 层2步上来的,所以状态转移方程非常容易的就得出了:dp[n] = dp[n-1] + dp[n-2]。 由于斐波那契额数列的求解可以用递归,所以博主最先尝试了递归,拿到 OJ 上运行,显示 Time Limit Exceeded,就是说运行时间超了,因为递归计算了很多分支,效率很低,这里需要用动态规划 (Dynamic Programming) 来提高效率,代码如下:

C++ 解法一:

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

Java 解法一:

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        int[] dp = new int[n];
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

我们可以对空间进行进一步优化,只用两个整型变量a和b来存储过程值,首先将 a+b 的值赋给b,然后a赋值为原来的b,所以应该赋值为 b-a 即可。这样就模拟了上面累加的过程,而不用存储所有的值,参见代码如下:

C++ 解法二:

class Solution {
public:
    int climbStairs(int n) {
        long a = 1, b = 1;
        while (n--) {
            b += a;
            a = b - a;
        }
        return a;
    }
};

Java 解法二:

public class Solution {
    public int climbStairs(int n) {
        long a = 1, b = 1;
        while (n-- > 0) {
            b += a; 
            a = b - a;
        }
        return a;
    }
}

虽然前面说过递归的写法会超时,但是只要加上记忆数组,那就不一样了,因为记忆数组可以保存计算过的结果,这样就不会存在重复计算了,大大的提高了运行效率,其实递归加记忆数组跟迭代的 DP 形式基本是大同小异的,参见代码如下:

C++ 解法三:

class Solution {
public:
    int climbStairs(int n) {
        vector<int> memo(n + 1);
        return helper(n, memo);
    }
    int helper(int n, vector<int>& memo) {
        if (n <= 1) return 1;
        if (memo[n] > 0) return memo[n];
        return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    }
};

Java 解法三:

public class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return helper(n, memo);
    }
    public int helper(int n, int[] memo) {
        if (n <= 1) return 1;
        if (memo[n] > 0) return memo[n];
        return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    }
}

论坛上还有一种分治法 Divide and Conquer 的解法,用的是递归形式,可以通过,但是博主没有十分理解,希望各位看官大神可以跟博主讲一讲~

C++ 解法四:

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

Java 解法四:

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

最后来看一种叼炸天的方法,其实斐波那契数列是可以求出通项公式的,推理的过程请参见 知乎上的这个贴子

Fn = (1 / sqrt(5))(((1 + sqrt(5)) / 2) ^ n - ((1 - sqrt(5)) / 2) ^ n)

那么有了通项公式后,直接在常数级的时间复杂度范围内就可以求出结果了,参见代码如下:

C++ 解法五:

class Solution {
public:
    int climbStairs(int n) {
        double root5 = sqrt(5);
        return (1 / root5) * (pow((1 + root5) / 2, n + 1) - pow((1 - root5) / 2, n + 1));
    }
};

Java 解法五:

public class Solution {
    public int climbStairs(int n) {
        double root5 = Math.sqrt(5);
        double res =  (1 / root5) * (Math.pow((1 + root5) / 2, n + 1) - Math.pow((1 - root5) / 2, n + 1));
        return (int)res;
    }
}

Github 同步地址:

https://github.com/grandyang/leetcode/issues/70

类似题目:

Min Cost Climbing Stairs

Fibonacci Number

N-th Tribonacci Number

Minimum Rounds to Complete All Tasks

Count Number of Ways to Place Houses

Number of Ways to Reach a Position After Exactly k Steps

Count Ways To Build Good Strings

Frog Jump II

参考资料:

https://leetcode.com/problems/climbing-stairs/

https://leetcode.com/problems/climbing-stairs/discuss/25345/Easy-solutions-for-suggestions.

https://leetcode.com/problems/climbing-stairs/discuss/25296/3-4-short-lines-in-every-language

https://leetcode.com/problems/climbing-stairs/discuss/25608/My-divide-and-conquer-way-to-solve-this-problem(Java)

https://leetcode.com/problems/climbing-stairs/discuss/25436/Using-the-Fibonacci-formular-to-get-the-answer-directly

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation