题目
题目链接
剑指offer：斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
解题思路
斐波那契数列属于经典的递归问题，对于这题的求解，我们首先要知道斐波那契数列的状态转移式，即f[n]=f[n-1]+f[n-2]，且在n=1或2时，f[n]=1。
在理解基础的状态转移式后，最容易想到的便是递归调用，但很遗憾，这样算法的时间复杂度往往达不到要求。
仔细观察后可以发现，每次求解的f[n]都在之后两个f[n]的求解中起作用，因此我们可以将其保存，这样能够避免重复计算，降低算法的时间复杂度；同时，因为只在后续两个f[n]的求解中起作用，因此只需要保存两个f[n]的值即可。
具体代码
class Solution {
public:
int Fibonacci(int n) {
if (n < 0)
return -1;
if (n <= 1)
return n;
int sum = 1; // f[n-1]
int pre = 0; // f[n-2]
for (int i = 2; i <= n; ++i) {
// 更新f[n-1]和f[n-2]
sum = sum + pre;
pre = sum - pre;
}
return sum;
}
};