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

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

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

题目链接：/229.html

一、题目描述

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

F(0)=0,F(1)=1F(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

二、题目解析

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

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

classSolution{publicintfib(intn){if(n<=0)return0;if(n==1)return1;return(fib(n-1)+fib(n-2))%1000000007;}}

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

举个例子，n = 10。

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

模拟：模拟题目的运行。

规律：尝试总结出题目的一般规律和特点。

匹配：找到符合这些特点的数据结构与算法。

边界：考虑特殊情况。

1、模拟

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

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

2、规律

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

如何避免重复计算？

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

3、匹配

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

4、边界

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

三、动画理解

四、参考代码

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

五、复杂度分析

时间复杂度

时间复杂度为 O(N) 。

空间复杂度

空间复杂度为 O(N)。

六、相关标签

递归

记忆化

备忘录

动态规划

更多算法内容请访问 AlgoMooc 官网：，一个提供算法图解的平台，从此，刷题不再枯燥。