《剑指offer》 第10题 斐波那契数列

题目描述
现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

有一道跳台阶的与本题相似，只是初始条件不同。(关于青蛙跳台阶那题，我在牛客先做的，因此那个题解的思考过程可能比本篇详细)
斐波那契数列的初始条件是f(0)=0,f(1)=1
f(2)=f(0) + f(1) 从角标2就可以开始递推，而跳台阶（只能跳1阶或2阶）的方式，递推是从f(3)开始，因此除了初始条件不同，思路完全可以借鉴

1. 思路1：暴力解法，标记出初始条件后，就可以进行递归调用了。

   public class Solution {
      public int Fibonacci(int n) {
       if (n < 1) {
          return 0;
       }
      if (n == 1 ) {
         return n;
       }
     return Fibonacci(n - 1) + Fibonacci(n - 2);
     }
   }

2. 思路2：可以看到递归是反复调用的，有些值可能会重复计算，f(n-1)和f(n)在调用递归时，都会用到f(n-2)，此时f(n-2)就会重复计算，为了避免反复进行重复计算，我们对已经计算过的值可以利用数组存起来，需要用的时候，直接调值即可

   public class Solution {
   
     public int Fibonacci(int n) {
        int[] arr = new int[n+1];//创建数组赋值 为了n=0时避免数组越界，因此+1
        for(int i =0;i<=n;i++){   //给数组赋初值，之后检查，判断仍为初始值，允许调用递归
          arr[i]=-1;
        }
        return fib(n,arr);
     }
     public int fib(int n,int[] arr){
        if (n < 1) {
          return 0;
        }
        if (n == 1 ) {
          return n;
        }
        if(arr[n] == -1 ){//如果等于，说明没算过，允许递归调用计算，并将结果赋值
          arr[n] =fib(n - 1,arr) + fib(n - 2,arr);
        }
        return arr[n]; //如果不等于，说明已经计算过，直接返回。避免再次调用递归计算
    }
   }

3.思路3 动态规划，自下而上的思路，从小推导到大
数组实现方式：

public class Solution {

  public int Fibonacci(int n) {
     int[] arr = new int[n+1];//创建数组，这里可以不用赋值，如果没记错，java默认创建的都是0
     return fib(n,arr);
 }
  public int fib(int n,int[] arr){
     if(n==0) return arr[0]=0;  //上面防了，这里也要防越界，当n为0时不能给角标为1的赋值
     if(n==1) return arr[1]=1; 
    //arr[0]其实可以先赋值，区别不大，但arr[1]必须保证n不为0的情况才能赋值
      arr[0]=0;
      arr[1] =1;
     for(int i=2;i<=n;i++){ //这里直接计算就好了
         arr[i] = arr[i-1]+arr[i-2];
     }   
     return arr[n];
   }
}

不用数组的动态规划，上面需要开辟新数组，空间复杂度高了，可以只用三个变量就可以完成，代码如下

public class Solution {

  public int Fibonacci(int n) {
     int first = 0;
     int second = 1;
     int result = 0;
     if(n==0) return 0;//return first;
     if(n==1) return 1;//return second;
     for(int i = 2; i <= n; i++) {
         result = second+first;     //例如f(5)=f(4)+f(3)
         first = second;            //重新赋值，代替原本f(3)位置的数
         second = result;           //重新赋值，代替原本f(4)位置的数
     }
     return result;
  }
}