剑指offer JZ10斐波那契数列

很多同学在刚开始学习递归时，斐波那契数列是一个经典的例子，在解决此题中，递归的思想同时扮演着重要的角色。

解法1：

class Solution {
public:
    int Fibonacci(int n) {
      if(n<=2)  
          return 1; //先解决n=1或2的特殊情况
        else
            return Fibonacci(n-1)+Fibonacci(n-2); //调用函数，例如 求f(3)时，f(3)=f(2)+f(1);
                                                  // 同理f(4)=f(3)+f(2);层层向内调用，直到求出值
    }
};

这种解法的优点是思路清晰，代码简单，但是递归的调用，导致空间复杂度过于的即 递归中生成栈的空间。且存在很多次的重复计算：

 为了减少重复计算造成的不必要空间开支，我们可以采用c++中的map容器来存储已经计算过的

f(n)

class Solution {
public:
     map<int,int> map_flag;//记录已经被计算出来的值
    int Fibonacci(int n) {
        if(n<=1) return n;//f(0)=0,f(1)=1,初始状态
        if(map_flag.count(n)){//已经被计算过;采用count的函数可以降低内存与时间；
            return map_flag[n];//第n项的值
        }
        return  map_flag[n]=Fibonacci(n-1)+Fibonacci(n-2);//未被计算过，存入map;
    }
};

为了进一步减少空间和时间复杂度。我们尝试使用递归改迭代的方式

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=1)return n;//特别判断斐波拉契数列前两项值 f(0)=0; f(1)=1
        int l1=0,l2=1;//用来保留前两项的值
        for (int i=2; i<=n; ++i) {
            int temp=l1+l2;    //第一次temp值为前后两项的和
            l1=l2;             // l1记录当前项
            l2=temp;           //l2记录不包扩当前项的累和
        }
        return l2;          //返回总和
    }
};

空间复杂度为常数阶o(1),时间复杂度为o(n).