继续创造，加速生长！这是我参加「日新计划 10 月更文挑战」的第11天，点击检查活动概况

⭐ 算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能呈现的过错，以实战习题的方式理解算法，使用算法。

本文已收录于算法刷题系列专栏： 算法题解 欢迎订阅，继续更新。

欢迎重视 点赞 保藏⭐ 留言

代码成就万世基，积沙镇海；愿望永在凌云意，神采飞扬；

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

办法一：数学

思路

依据题意，能够知道这是斐波那契数列，那就直接套用公式：

接着咱们就能够经过这个公式直接求第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个台阶，问有几种办法？

这里能够选用逆向思维，即跨过最终一步或者两步就抵达了楼顶，这样如此反复进行逆推，因此能够总结出如下公式：

它意味着爬到第 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;
    }
}

后记

以上便是 【算法题解】 Day11 数学 的所有内容了，创造不易，多多支持

我是 ，期待你的重视

系列专栏： 算法题解