剑指 Offer 10- I. 斐波那契数列,斐波拉契,递归优化法,动态规划法,及其优化

剑指 Offer 10- I. 斐波那契数列,斐波拉契,递归优化法,动态规划法,及其优化

Lan
Lan
2023-01-14 / 0 评论 / 70 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2023年01月15日,已超过544天没有更新,若内容或图片失效,请留言反馈。

前言

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]

www.lanol.cn
对比一下老方法。
www.lanol.cn
我已经不想等了,没有对比就没有伤害,在这个空间不值钱的时代,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

时间对比,有进步,但不多,反正比原始递归强。
www.lanol.cn

源视频

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

www.lanol.cn

0

评论 (0)

取消