专栏首页五分钟学算法剑指 offer 面试题精选图解 10-I.斐波那契数列

剑指 offer 面试题精选图解 10-I.斐波那契数列

大家好,我是程序员吴师兄,欢迎来到图解剑指 Offer 专栏,在这个专栏里我将和大家一起学习如何用合理的思维来思考、解题、写代码。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题10- I. 斐波那契数列

题目链接:https://www.algomooc.com/229.html

一、题目描述

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 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

提示:

  • 0 <= n <= 100

二、题目解析

似乎学校的老师讲 递归 的时候都喜欢拿 斐波那契数列 举例。

因为,很容易就写出下面的代码。

class Solution {
    public int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return (fib(n-1) + fib(n-2)) % 1000000007;
    }
}

结果也很明显,无脑的递归暴力解法包含了大量的重复计算,提交上去直接标红提示超出时间限制

举个例子,n = 10。

接下来,我们依旧用 四步分析法 来分析一下这道题目。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

观察递归树,不难发现,在这棵树上有 很多结点是重复的 ,而且重复的结点数会随着 n 的增大而急剧增加,比如 fib(8) 被计算了两次,并且,以 fib(8) 为根的这个递归树体量巨大,多算一遍,会耗费巨大的时间。

事实上,用递归方法计算的时间复杂度是以 n 的指数的方式递增的

2、规律

即然耗时的原因是重复计算,我们只要想办法避免重复计算就行了

如何避免重复计算?

找一个合适的 数据结构 在递归的过程中存储计算的值,重复遇到某数字则直接从该 数据结构 中取用,避免重复计算。

3、匹配

这个合适的数据结构可以用 数组

4、边界

初始情况只有一个数或者两个数

三、动画理解

四、参考代码

//访问网站,获取更多题解:https://www.algomooc.com
class Solution {
    public int fib(int n) {
        //边界判断
        if(n == 0) return 0;
        //用于存储第 0 到 n 个数对应的值
        int[] dp = new int[n + 1];
        //先定义好第一个数
        dp[0] = 0;
        //再定义好第二个数
        dp[1] = 1;
        //计算大于 0 和大于 1 的值
        for(int i = 2; i <= n; i++){
            //当遇到之前计算过的数时,将不再递归往下找,直接用记忆化结果
            dp[i] = dp[i-1] + dp[i-2];
            //题目要求进行取模处理
            dp[i] %= 1000000007;
        }
        //返回结果
        return dp[n];
    }
}

五、复杂度分析

时间复杂度

时间复杂度为 O(N) 。

空间复杂度

空间复杂度为 O(N)。

六、相关标签

  • 递归
  • 记忆化
  • 备忘录
  • 动态规划

更多算法内容请访问 AlgoMooc 官网:https://www.algomooc.com,一个提供算法图解的平台,从此,刷题不再枯燥。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer - 面试题10- I. 斐波那契数列

    写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

    Michael阿明
  • 剑指Offer LeetCode 面试题10- I. 斐波那契数列

    写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

    TrueDei
  • 剑指 Offer 10- I. 斐波那契数列

    写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。

    Vincent-yuan
  • 剑指 Offer(C++版本)系列:剑指 Offer 10- I 斐波那契数列

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指Offer面试题:8.斐波那契数列

      很多C/C++/C#/Java语言教科书在讲述递归函数的时候,大多都会用Fibonacci作为例子,因此我们会对这种解法烂熟于心:

    Edison Zhou
  • LeetCode刷题记录:剑指 Offer 10- I. 斐波那契数列

    解题思路: 根据输入的 n 声明一个数组,定义好数组的前两个元素(即第 0 项和第 1 项),从第三个元素开始遍历数组,使数组的每一个元素等于前两个元素之和。...

    英雄爱吃土豆片
  • 剑指offer第7题:斐波拉契数列

    对于斐波拉契数列的使用,我们只需要知道通项公式,然后依次从第一项一直推导到第n项即可。根据题目中给出的通项公式

    鹏-程-万-里
  • 剑指 Offer(C++版本)系列:剑指 Offer 10- II 青蛙跳台阶问题

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指offer【10~19】

    f(n) = f(n-1) + f(n-2) + ... + f(0),其中 f(i) 表示从第 i 层跳到第 n 层的跳法。化简的 f(n) = 2 * f(...

    echobingo
  • 剑指 Offer(C++版本)系列:剑指 Offer 11 旋转数组的最小数字

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指 Offer(C++版本)系列:剑指 Offer 12 矩阵中的路径

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 面试题精选:神奇的斐波那契数列

    斐波那契数列,其最开始的几项是0、1、1、2、3、5、8、13、21、34…… ,后面的每一项是前两项之和,事实上,斐波那契在数学上有自己的严格递归定义。

    xindoo
  • 剑指 Offer(C++版本)系列:剑指 Offer 13 机器人的运动范围

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 每日算法题:Day 4

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39

    算法工程师之路
  • 每天一道剑指offer-牛客网跳台阶

    乔戈里
  • 剑指 offer -- JavaScript 版(1-11)

    本文为8月牛客网《剑指 offer》刷题做得,现整理出来作为参考。 虽然是算法题,但本文用 JavaScript 编写,看了《剑指 offer》以后发现很多问题...

    前端迷
  • 剑指offer(10-12)题解

    萌萌哒的瓤瓤
  • 【剑指offer】8.斐波那契数列

    题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

    ConardLi
  • 算法学习笔记

    这是一个算法题目合集,题目是我从网络和书籍之中整理而来,部分题目已经做了思路整理。问题分类包括:

    芋道源码

扫码关注云+社区

领取腾讯云代金券