剑指offer Leetcode 10 I .斐波那契数列

解法1：效率低的解法

复杂度

速度十分缓慢，重复计算太多

代码

//未考虑溢出和取模class Solution {public:int fib(int n) {if(n <= 0)return 0;if(n == 1)return 1;return fib(n - 1) + fib(n - 2);}};

解法2：

复杂度：

时间复杂度O(n)

代码

class Solution {public:int fib(int n) {if(n <= 0)return 0;if(n == 1)return 1;//fib(n - 1)与fib(n - 2)long long fibNMinusOne = 1;long long fibNMinusTwo = 0;long long fibN = 0;for(int i = 2; i <= n; i++){//新的值都是在这里算出，只要这里取模就够了fibN = (fibNMinusOne + fibNMinusTwo) % 1000000007;fibNMinusTwo = fibNMinusOne ;fibNMinusOne = fibN ; }return fibN;}};