1. 首页
  2. LeetCode

每日一道 LeetCode (17):爬楼梯

每日一道 LeetCode (17):爬楼梯

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:爬楼梯

题目来源:https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

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

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

注意:给定 n 是一个正整数。

示例 1:

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

示例 2:

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

解题过程

过程啥过程,这道题完全没有头绪好么。

好不容下班后爬了个 7 层楼回家,结果打开电脑接着让我爬楼梯,爬个锤子哦。

每日一道 LeetCode (17):爬楼梯

最近的题是怎么了,明明说好了是简单难度,结果还是一眼看下去连想法都没,让我回归下前两天的那些题它不好么。这道题我有一种强烈的预感是一道数学题,和程序关系不是很大。

么得办法,不会做就只能打开答案开始看答案了。

解题方案一:动态规划

说是动态规划,实际上是对题做了一个简单的推演:

输入    输出
1       1
2       2
3       3
4       5
5       8
...

看着是不是感觉很符合这个公式:

f(x) = f(x - 1) + f(x - 2)

这个公式其实很好理解,因为最后一次要么上 1 个台阶,要么是上 2 个台阶,上一个台阶前面的种数有 f(x – 1) 种,上 2 个台阶前面有 f(x – 2) 中方式,所以 f(x) 就是这两个加起来咯。

对着这个公式写代码其实很简单:

public int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}

每日一道 LeetCode (17):爬楼梯

解题方案二:斐波那契数列

我们把这个题结果的数列列出来看一下:

1, 2, 3, 5, 8, 13, 21 ...

如果上大学的时候没有偷懒的话,这个数列应该很有名,它是斐波那契数列,又叫黄金分割数列。

有关斐波那契是由一个通项公式的:

f(n) = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2}) - (\frac{1 - \sqrt{5}}{2})]

有了这个通项公式,写代码应该没啥问题了,照着写就好了。

至于这个通项公式的推导,我就不介绍了,感兴趣的同学可以自己百度去查,主要是这个公式打起来真的很费劲。

public int climbStairs_1(int n) {
    double sqrt5 = Math.sqrt(5);
    // 题目下标从 0 开始,因此求 n + 1
    double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
    return (int)(fibn / sqrt5);
}

每日一道 LeetCode (17):爬楼梯

其实答案中还有一个方案是叫 「矩阵快速幂」 ,这个思想我了解清楚了,但是答案中给的题解没咋看懂。

原谅我把大学的线性代数都不知道扔哪里去了,今天晚上基本上研究了半个晚上矩阵也没大懂,主要是年纪大了,以前学的东西都忘得差不多了。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code