70. 爬楼梯

题目

70. 爬楼梯 难度：easy

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 45

方法一：数学

思路

根据题意，可以知道这是斐波那契数列，那就直接套用公式：

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

接着我们就可以通过这个公式直接求第 n 项了。
 

解题

Python：

class Solution:
    def climbStairs(self, n: int) -> int:
        import math
        sqrt5 = 5 ** 0.5
        fibn = math.pow((1 + sqrt5) / 2, n + 1) - math.pow((1 - sqrt5) / 2, n + 1)
        return int(fibn / sqrt5)

Java：

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

方法二：动态规划

思路

根据题意，需要爬 n 阶楼梯才能到达楼顶，并且每次只能爬1或2个台阶，问有几种方法？

这里可以采用逆向思维，即跨越最后一步或者两步就到达了楼顶，这样如此反复进行逆推，因此可以总结出如下公式：

$$ f(n) = f(n-1) + f(n-2) $$

它意味着爬到第 n 级台阶的方案数是爬到第 n−1 级台阶的方案数和爬到第 n−2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(n) 只能从 f(n - 1) 和 f(n - 2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1) = 1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。

p = 0
q = 0
r = 1
for ...:
    p = q
    q = r
    r = p + q

解题

Python：

class Solution:
    def climbStairs(self, n: int) -> int:
        res = [1, 2]
        if n <= 2:
            return res[n-1]
        for i in range(2, n):
            res.append(res[-1] + res[-2])
        return res[-1]

Java：

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

509. 斐波那契数

题目

509. 斐波那契数 难度：easy

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入： n = 2
输出： 1
解释： F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入： n = 3
输出： 2
解释： F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入： n = 4
输出： 3
解释： F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

方法一：数学

思路

参照上题思路；

解题

Python：

class Solution:
    def fib(self, n: int) -> int:
        sqrt5 = 5**0.5
        fibN = ((1 + sqrt5) / 2) ** n - ((1 - sqrt5) / 2) ** n
        return round(fibN / sqrt5)

Java：

class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
        return (int) Math.round(fibN / sqrt5);
    }
}

方法二：动态规划

思路

参照上题思路；

解题

Python：

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        p, q, r = 0, 0, 1
        for i in range(2, n + 1):
            p, q = q, r
            r = p + q
        
        return r

Java：

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

后记

📝 上篇精讲： 【算法题解】 Day10 BFS | DFS
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解