力扣|力扣 - 剑指 Offer 10- I. 斐波那契数列力扣-剑指Offer10-I.斐波那契数列

题目剑指 Offer 10- I. 斐波那契数列
思路1（递归 / 自顶向下）

这题是很常见的一道入门递归题，可以采用自顶向下的递归方法，比如我们要求第n个位置的值，根据斐波那契数列的定义fib(n) = fib(n-1) + fib(n-2)，即等于前一个和前前一个两个的值之和
但是如果直接递归，会导致很多重复的计算，效率很低，比如 n 为 5 时：
1. fib(5) 为 fib(4) 和 fib(3) 两个值之和
2. 然后 fib(4) 又等于 fib(3) 和 fib(2) 两个值之和。注意， fib(3) 在上一步已经求过了，这里还要再求一次
3. 另一个 fib(3) 即为 fib(2) 和 fib(1) 两个值之和，同样，fib(2)，也被求过了
4. ……
  
  文章图片
【力扣|力扣 - 剑指 Offer 10- I. 斐波那契数列】根据上面例子我们可以发现这样子会导致很多多余的计算，做无用功，也会出现由于 n 的增大导致计算量急剧增大。因此我们可以将这个算法优化一下，就是添加一个表格 memory 来记录计算过的值，在每次递归的时候，判断一下之前是否计算过了，如果发现计算过了，直接返回数组中对应的值，否则就计算一下，然后记录到 memory 表格里

代码

class Solution {int[] memory; public int fib(int n) { memory = new int[n+1]; return help(n); }public int help(int n) { // 递归结束的条件 if (n <= 1) { return n; }// 判断是否计算过了 if (memory[n] != 0) { return memory[n]; }// 没有在 memory 中找到就计算一下，然后在记录到 memory 中 int i = help(n - 1) + help(n - 2); i %= 1000000007; memory[n] = i; return memory[n]; } }

复杂度分析

时间复杂度：\(O(N)\)
空间复杂度：\(O(N)\)

思路2（迭代 / 动态规格）

同样，根据斐波那契数列定义，可以发现第 n 个的值为前两个值之和，因此我们可以从第一个开始计算，循环计算到 n就得到了结果，空间上仅仅占两个变量的空间，为 \(O(1)\) ，代码如下：

代码

class Solution { public int fib(int n) { if (n < 2) { return n; }int a = 1; int b = 1; for (int i = 2; i < n; i++) { int temp = (a + b); a = b; b = temp; b %= 1000000007; }return b; } }

复杂度分析