题目链接：剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode）
朴素递归做法
核心是一个递归边界和递归体，复杂度分析可画递归树可得，时间复杂度是O(2N)，这是一个估算的上界，递归树最坏情况并不是满二叉树，数学上已经有证明出有通项公式可以表示：
而
。 空间复杂度和递归调用时的栈深有关是O(N)，显然有很多次的重复调用：
1 class Solution {
2 public int fib(int n) {
3 if(n == 0 || n == 1) {
4 return n;
5 }
6 return fib(n - 1) + fib(n - 2);
7 }
8 }
尾递归做法
这是一种自下而上（递归树）的做法，时间复杂度显然是O(N)，空间复杂度因为不需要函数调用栈所以是O(1)：
1 int fib(int x1, int x2, int n) {
2 if (n == 0 || n == 1) {
3 return n;
4 } else if (n == 2) {
5 return x1 + x2;
6 } else {
7 return fib(x2, x1 + x2, n - 1);
8 }
9 }
迭代做法
其实和尾递归的思想是一样的，也是一种自下而上的做法，时间复杂度显然是O(N)，空间复杂度所需要的额外变量都是常数数量级所以是O(1)：
1 class Solution {
2 public int fib(int n) {
3 if(n == 0 || n == 1) {
4 return n;
5 }
6 int f0 = 0;
7 int f1 = 1;
8 int tmp = 0;
9 for(int i = 0; i <= n - 2; i++) {
10 tmp = (f0 + f1) % 1000000007;
11 f0 = f1;
12 f1 = tmp;
13 }
14 return tmp;
15 }
16 }
这里为啥要对1000000007（1e9+7）取模呢，因为溢出的问题，当然你也可以抛出一个异常，1000000007是一个足够大的质数（意味着没有公约数）：
动态规划
已知状态转移方程，利用滚动数组思想优化，时间复杂度是O(N)，空间复杂度是O(1)：
1 class Solution {
2 public int fib(int n) {
3 if(n == 0) {
4 return 0;
5 }
6 int[] dp = new int[n + 1];
7 dp[0] = 0;
8 dp[1] = 1;
9 for(int i = 2; i <= n; i++) {
10 dp[i] = dp[i-1] + dp[i-2];
11 dp[i] %= 1000000007;
12 }
13 return dp[n];
14 }
15 }
1 class Solution {
2 public int fib(int n) {
3 if (n < 2) {
4 return n;
5 }
6 int p = 0, q = 0, r = 1;
7 for (int i = 2; i <= n; ++i) {
8 p = q;
9 q = r;
10 r = (p + q) % 1000000007;
11 }
12 return r;
13 }
14 }
矩阵快速幂
利用矩阵性质：
引入快速幂：
核心的思想是减少乘法的次数，比如710 = (72 * 72 * 7)2，只需要进行4次乘法即可。
1 int quickPow(int a, int n){
2 int ans = 1;
3 while(n){
4 if(n&1) //如果n的当前末位为1
5 ans *= a; //ans乘上当前的a
6 a *= a; //a自乘
7 n >>= 1; //n往右移一位
8 }
9 return ans;
10 }
通项公式法
这个快用之前介绍的通项公式直接可以得出答案时间和空间复杂度都是O(1)。
推导：https://www.zhihu.com/question/25217301/answer/30247743
标签：return,递归,int,复杂度,fib,幂到,Fibonacci,logN,通项 From： https://www.cnblogs.com/RQfreefly/p/17064372.html