大家好，我是程序员吴师兄，欢迎来到图解剑指 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、边界
初始情况只有一个数或者两个数
三、动画理解
隐藏内容
此处内容需要权限查看
会员免费查看四、参考代码
//访问网站，获取更多题解：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)。
六、相关标签
- 递归
- 记忆化
- 备忘录
- 动态规划
