题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n≤39

输入：4
返回值：3

算法思路

斐波那契数列的标准公式为：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

代码实现

递归

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

时间复杂度：O(2ⁿ)
空间复杂度：O(1)

优化递归

递归会重复计算大量相同数据，我们用个数组把结果存起来。也就是备忘录

public class Solution {
    public int Fibonacci(int n) {
        int [] res = new int[40];
        res[0] = 0;
        res[1] = 1;
        for(int i=2;i<=n;i++){
            res[i] = res[i-2] + res[i-1];
        }
        return res[n];
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

优化存储

其实我们可以发现每次就用到了最近的两个数，所以我们可以只存储最近的两个数

sum 存储第 n 项的值
one 存储第 n-1 项的值
two 存储第 n-2 项的值

public class Solution {
    public int Fibonacci(int n) {
        if(n<=1){
            return n;
        }
        int sum = 0;
        int one = 0;
        int two = 1;
        for(int i=2;i<=n;i++){
            sum = one + two;
            one = two;
            two = sum;
        }
        return sum;
    }
}