推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，

请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39。

public class Solution {
    public int Fibonacci(int n) {

    }
}

思路：

首先要知道斐波那契数列的公式 
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 == 0){
            return 0; //第0项直接输出0
        }else if(n == 1){
            return 1;  //第1项直接输出1
        }
        int sum = 0; 
        int sum_1 = 1; //n-1个数
        int sum_2 = 0; //n-2个数
        for(int i=2; i<=n; i++){
            sum = sum_1 + sum_2;
            sum_2 = sum_1;
            sum_1 = sum;
        }
        return sum;
    }
}

这个实现，其实还可以优化：

上面实现中， sum 只有在最后输出时，才是我们要的值。

而如果还有下一次循环，那么 sum  就是 n-1项， sum_1 就是 n-2 项

实现优化：

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

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！