剑指offer 10. 斐波那契数列

2020年12月2日 周三 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

---

这道题其实思路比较简单，但是如果计算出最后结果再取模的话，在计算过程中就会造成大数溢出。解决办法就是，边计算边取模，结果和最后取模是一样的。之所以可以这样做，就是依据下面这个取模分配律：

具体代码如下：

class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        int first = 0, second = 1, sum = 0;
        for(int i=0;i<n-1;++i){
            sum = (first + second) % 1000000007;
            first = second;
            second = sum;
        }
        return sum;
    }
};

---

参考文献
《剑指offer 第二版》
https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/mian-shi-ti-10-i-fei-bo-na-qi-shu-lie-dong-tai-gui/