算法分析（七）：斐波那契数列
前言
这道题就是找出这个数列的第 n 个节点，而这个数列有个特地点就是第 n 个数字 = n-1 + n-2 两个数字之和，所以我们一般这种有两种解法，递归和迭代
题目地址：leetcode-cn.com/problems/fe…
第一种解法：迭代法
看到这种一个数等于前两个数之和的题目，第一个想法就需要存储以前的数字，一般都是用数组
第一步，创建一个数组
第二步，给前两个数组复制0 和 1
第三步，进行循环遍历，第 n 个数 = 第 n-1 个数 + 第 n-2 个数，然后存起来
第四步，将数组下标为 n 的数字返回
代码如下：
class Solution { public int fib(int n) { int[] ans = new int[105]; ans[0] = 0; ans[1] = 1; if(n==0) return 0; if(n==1) return 1; for(int i=2;i<=n;i++){ ans[i] = (ans[i-2] + ans[i-1])%1000000007; } return ans[n]; } } 复制代码但是你想想，如果第 n 个数足够大，那岂不是要创建一个很大的数组，但是数组除了第 n-1 个数和第 n-2 个数是有用的，之前的都是没用的，所以我们使用双指针法
使用两个指针分别指向第 n-1 个数和第 n-2 个数，然后每次循环就替换这两个指针
代码如下：
class Solution { public int fib(int n) { if(n == 0){ return 0; } if(n == 1){ return 1; } int pre = 0; int cur = 1; int sum = 0; for(int i=2;i<=n;i++){ sum = (pre + cur)%1000000007; pre = cur; cur = sum; } return sum; } } 复制代码第二种方法：递归法
虽然我觉得上面的方法足够简便，并且时间和空间都挺好，但是我还是要说这种递归算法，可能性能不如上面的，但是思想还是要学习一下
先看下图，斐波那契数列给划分下来，就类似于树结构
所以我们递归也很简单就是下面的代码，将结果分散下去：
class Solution { public int fib(int n) { if(n == 0){ return 0; } if(n == 1){ return 1; } return fib(n-1) + fib(n-2); } } 复制代码但是这个代码还是有点不够好，因为我们做了很多的重复性操作，就如下图花了红圈的地方，我们可以用一个数组来保存，然后节省时间。
class Solution { public static int[] cache = new int[101]; public int fib(int n){ if (0 == n || 1 == n) return n; if (0 != cache[n]) return cache[n]; cache[n] = (fib(n - 1) + fib(n - 2)) % 1000000007; return cache[n]; } } 复制代码总结
总体来说我还是更喜欢双指针的那种解法，因为更加简便，但是递归还是必学的，思想永远不会嫌多的。
作者：程序胖
链接：https://juejin.cn/post/7028367195159658509