☀（day39）

目录

题目：

题目分析：

解题思路：

解法一：常规解法

代码实现

解法一：动态规划

代码实现

题目：

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

F(0) = 0，F(1) = 1

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

⭐示例 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

⭐示例 2：

输入：n = 4

输出：3

解释：F(4) = F(3) + F(2) = 2 + 1 = 3

题目分析：

斐波那契数列的初始值为0和1，下一个值等于前两个值之和。题目给出的n代表斐波那契数列的索引，需要输出索引对应的值。

解题思路：

解法一：常规解法

既然下体个数是上两个数之和，那么我们就用一个列表储存每次计算出的数，接着根据给定的n计算n索引对应的数。

代码实现

def fib(n):
    lst = [0, 1]
    lst = [0, 1]

    if n == 0:
        return 0
   
    while i <= n-2:
        lst.append(lst[i] + lst[i+1])
        i += 1
    return lst[-1]

在while循环中需要进行n次运算，时间复杂度为O(n)。使用列表储存n个斐波那契数列，空间复杂度为O(n)。

解法一：动态规划

因为斐波那契数列中的任一个数都是前两个数之和，所以我们只需保留前两个数即可计算当前位置的斐波那契数，不需要使用列表将所有的数都记录下来。在动态规划中我们可以不断更新前两个数即可，通过前两个数计算当前的数即可。

代码实现

def fib(n):
    if n <= 1:
        return n

    p1, p2, r = 0, 0, 1
    for i in range(2, n + 1):
        p1, p2 = p2, r
        r = p1 + p2

    return r

在for循环中需要进行n次计算，时间复杂度为O(n)， 使用变量“储存”前两个数，空间复杂度为O(1)。

今天就到这，明天见。

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄