1、题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
2、分析
这个问题其实已经是一个老生常谈的问题了，最常见的解决办法有三种，第一种就是常见的教科书级别的递归，但是这个有一个很大的问题就是很容易爆栈。第二种是用循环，中间记录上一步计算的结果。第三种是用数学公式。递归可以不用去考虑，最需要掌握的是第二种。
3、代码
class Solution {
public:
int Fibonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 1;
long res;
int mid1=1;
int mid2=1;
for(int i=3;i<=n;++i){
res=mid1+mid2;
mid1=mid2;
mid2=res;
}
return res;
}
};
4、相关知识点
斐波那契的相同类型题有很多，比如上台阶问题等等。
