题解 | #斐波那契数列#

数组中保存计算第n个斐波那契数的n-1的值，与n-2个值，便于计算；

F1：

public class Solution {
    public int Fibonacci(int n) {
        //n = 1 ,2 时直接返回
        if(n == 1 || n == 2){
            return 1;
        }
        //大于2时，创建长度为2 的数组，初始值为1
        int[] ints = {1,1};
        //count表示已经计算出的数的个数，由于1，2时为1，所以count初始值为2
        int count = 2;
        //循环只要count的值小于n，那么就说明第n个斐波那契数还没有被计算出来
        for (int i = 2; count < n ; count += 2) {
            //更新数组中的下标1，2的值
            ints[0] += ints[1];
            ints[1] += ints[0];
        }
        //如果是偶数返回下标1的值
        if (n % 2 == 0){
            return ints[1];
        }
        //如果是奇数返回下标0的值;
        return ints[0];
    }
}

F2:递归调用函数，时间复杂度，空间复杂度较高；

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