大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39

掌握思路：原始递归算法效率太低，所以不予采用。我用的是时间复杂度为O(n)的一个算法：重点在while循环中，当n>=2时，按照已知f(n-1)、f(n-2)计算f(n)，再将f(n),f(n-1)的值保存计算下一个值，就这样从下往上计算。

代码：

class Solution {
public:
    int Fibonacci(int n) {
        int f[2]={0,1};
        if(n==0)
            return f[0];
        if(n==1)
            return f[1];
        //从下往上计算。
        int f_n0=f[0];
        int f_n1=f[1];
        int f_n2=0;
        if(n>1)
        {
            for(int i=2;i<=n;i++)
            {
                f_n2=f_n0+f_n1;
                f_n0=f_n1;
                f_n1=f_n2;
            }
        }
        return f_n2;
    }
};

与上述代码一样的

发现计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]...f[0],所以保存f[2]..f[0]是浪费了空间。
只需要用3个变量即可。

int Fibonacci(int n) {
        if (n < 0)
            return -1;
        if (n == 0 || n == 1)
            return n;

        int a = 0,b = 1,c=0;
        int i = 2;
        while (i<=n)
        {
            c = a + b;
            a = b;
            b = c;
            ++i;
        }
        return c;
    }

差点意思但用的动态规划思想

int Fibonacci(int n)
    {
        if (n < 0)
            return -1;
        if (n == 0 || n == 1)
            return n;
        vector<int> fibo(n+1,0);
        fibo[0] = 0; fibo[1] = 1;
        int i = 2;
        while (i<=n)
        {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
            ++i;
        }
        return fibo[n];
    }