剑指offer | 10.斐波那契数列

小咪咪 2022-12-22 06:12 89阅读 0赞

**题目内容**

> 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
> 
> F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
> 
> 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
> 
> 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

**示例 1：**

输入：n = 2
    输出：1

**示例 2：**

输入：n = 5
    输出：5

**提示：**

0 <= n <= 100

--------------------

**思路：**

*  第一反应：递归不就好了吗！然后我就挂了：

class Solution { 
    public:
        int fib(int n) { 
            double k;
            if(n==0 ||n==1) return n;
            else k=fib(n-1)+fib(n-2);
            return k%(1e9+7);
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]

*  看了大佬的讲解才意识到可能还没到最后结尾的时候就已经溢出了，因为中间过程很多都重复计算了。

**正解：**

class Solution { 
    public:
        int fib(int n) { 
           if(n==0)return 0;
           if(n==1)return 1;
           int N=0,NMinusOne=1,NMinusTwo=0;//注意是初始化NMinusOne=1,NMinusTwo=0
           while(n>=2){ 
               //采取从下往上的方法，吧计算过的中间项保存起来
               //避免重复计算导致递归调用栈溢出
               N=(NMinusOne+NMinusTwo)%1000000007;//不知道为啥写（1e9+7）就不行。
               NMinusTwo=NMinusOne;
               NMinusOne=N;
               n--;
           }
           return N;
        }
    };

![在这里插入图片描述][20201118082423364.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8f5d9416dd58445e9f6599ce24b341df.png
[20201118082423364.png_pic_center]: https://img-blog.csdnimg.cn/20201118082423364.png#pic_center