面试题10：斐波那契数列 - （1）求斐波那契数列的第n项（c++）【剑指offer】

纯递归：问题：程序未能在规定时间内运行结束。

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=0) return 0;
        if(n==1) return 1;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
};

改进：避免重复计算，解决方法：保存中间计算结果。

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=0) return 0;
        if(n==1) return 1;

        int fzero=0,fone=1,fn=0;
        for(int i=1;i<n;i++){
            fn=fone+fzero;
            fzero=fone;
            fone=fn;
        }
        return fn;
    }
};