斐波那契数列，剑指offer，力扣

目录

题目地址：

我们直接看题解吧：

解题方法：

难度分析：

审题目+事例+提示：

解题思路（动态规划）：

代码实现：

补充说明：

代码（优化）：

---

题目地址：

LCR 126. 斐波那契数 - 力扣（LeetCode）

难度：简单

今天刷斐波那契数列，大家有兴趣可以点上看看题目要求，试着做一下。

我们直接看题解吧：

解题方法：

方法1，递归（效率太慢）

会出现重复，例如f(5)=f(4)+f(3),f(4)=f(3)+f(2),此时f(3)重复了，此外，若递归过深则会造成栈溢出情况。

方法2，（递推）动态规划（或循环求余）

难度分析：

总体应该不算难，毕竟一般学校应该会用递归法讲这到题

审题目+事例+提示：

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。

解题思路（动态规划）：

由于斐波那契数列是0,1,1,2,3,5,8....即从0 开始，通过循环，逐步求出下一位数（n=(n-1)+(n-2)）,通过一个变量sum保存，类似于递增，因此不会出现重复的情况

代码实现：

class Solution {
    public int fib(int n) {
        if(n <= 0){        //判断若n=0，直接返回0
            return 0;
        }
        int a = 0,b = 1,sum = 0;
        for(int i = 0;i < n;i++){
            sum = (a + b) % 1000000007; //循环取模
            a = b;
            b = sum;            //sum相当于存不断累加的结果
        } 
        return sum;
    }
}

补充说明：

为什么res要模1000000007？

     

 因为这个数字是10位的最小质数，上面的代码并没有问题，只是数字太大会造成溢出，需要将计算结果 % 1000000007才能保证得出的结果在int 范围中

代码（优化）：

public int fib(int n) {
        int a=0, b=1,sum=0;
        // 当n>1时才会进入循环，所以for循环算的是n从2到n+1的值
        for(int i=2; i<=n+1; i++){
            sum=(a+b) % 1000000007;        
            a=b;
            b=sum;  
        }
        // 由于多算一次，所以返回的是a，不是b
        return a;
    }