剑指offer(7)----斐波那契数列

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。

题目分析：这个题没啥好说的，主要是用递归的确方便，但是要注意的就是在函数调用的时候会有栈帧开辟的消耗，而栈的资源有限，所以使用递归在n值很大的时候会出现栈溢出崩溃。所以这个题用循环最好。

C++代码： class Solution { public: int Fibonacci(int n) { /* if(n==0) return 0; if(n==1) return 1; if(n==2) return 1; int f1=1; int f2=1; int f3=1; for(int i=3;i<=n;++i) { f3=f1+f2; f1=f2; f2=f3; } return f3; } */ int i=0; int j=1; while(n-->0) //动态规划，第n项只和第n-1和第n-2有关，所以节省了重复值的存储空间 { j=j+i; i=j-i; } return i; } };