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

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

题目汇总链接:

https://www.algomooc.com/hi-offer

一、题目描述

写一个函数,输入 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、边界

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

三、动画理解

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、参考代码

//访问网站,获取更多题解: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)。

六、相关标签

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

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(3)