前言

b站摸鱼，看见了这个视频，妙呀。
先是递归，通过空间换时间。
又是动态规划，优化空间。
视频放在最后面了。
前面是我个人学习笔记。

笔记

递归法

up主直接三目运算符了，虽然代码简洁，但可读性体验感也会降低。
体谅一下将来的我，还能看懂，所以我这里就拆开了。
最基本的递归，求斐波拉契的第n项

def fb_dg(n):
    if n < 2:
        return n
    return fb_dg(n - 1) + fb_dg(n - 2)

如果要计算n项之和的话，就多了很多次重复的计算，因为每次都需要从n开始，一直减。
然后可以新建一个list(虽然字典无序+哈希，检索比list要快，时间复杂度为O(1)，而list为O(n)，但是好像我们这个直接根据下标，所以用list更快），并且需要创建n+1个初始值，防止出现下标越界的情况。用于存放每次计算的结果，如果没有结果再进行计算。
先来看一下效果，一个字6，本来想放毫秒的，但是它的实力不允许。

def fb_dg_zd(n, r: list):
    if n < 2:
        return n
    v = r[n]
    if v != -1:
        return v
    else:
        r[n] = fb_dg_zd(n - 1, r) + fb_dg_zd(n - 2, r)
        return r[n]

对比一下老方法。

我已经不想等了，没有对比就没有伤害，在这个空间不值钱的时代，666。
我想起了我之前公司项目的时候，也是用了空间换时间，我需要将某方案复制一份，包括其子项指标啥的一堆东西，是一个递归，然后我就用dict，建由于数据主键都是雪花id，所以每一条数据都是唯一的主键值，因此我只需要一个dict，并且直接存主键id即可，如果有就直接get，没有就新增进去，下次get就可以返回了，节省了很多时间。

动态规划法

def fb_dt(n):
    dp = [0, 1] + [-1 for _ in range(n - 1)]
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

优化空间之后，这个

def fb_dt_zd(n):
    if n < 2:
        return n
    pre, cur = 0, 1
    for i in range(2, n + 1):
        pre, cur = cur, pre + cur
    return cur

时间对比，有进步，但不多，反正比原始递归强。

源视频

Leetcode

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

class Solution:
    def __init__(self):
        self.r = []
        self.MOD = 10 ** 9 + 7

    def fib(self, n: int) -> int:
        if n < 2:
            return n
        if len(self.r) == 0:
            self.r = [-1 for _ in range(n + 1)]
        v = self.r[n]
        if v != -1:
            return v % self.MOD
        else:
            self.r[n] = self.fib(n - 1) + self.fib(n - 2)
            return self.r[n] % self.MOD