剑指Offer07: 斐波那契数列
题意
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39
思路
递归求解：超时打表求解：内存超限综合前两者，其实只需要一个长度为3的数组，然后根据下标模3运算得到当前index, 再求得前两位的index,相加更新当前位置即可。
代码
class Solution {
public:
int Fibonacci(int n) {
int F[3] = {0,1,1};
if(n==0 || n == 1 || n==2)
return F[n];
for(int i=3; i<=n;i++){
int sum = F[(i-1) % 3] + F[(i-2)%3];
if(i == n)
return sum;
F[i % 3] = sum;
}
}
};
反思
看了题后的讨论，其实可以不用开数组，直接用三个变量表示第i, i-1, i-2个数即可，伪代码如下：
int preprenum = 0, prenum = 1
for(int i=2;i<=n;i++){
result = preprenum + prenum;
preprenum = prenum;
prenum = result;
}
