#include <iostream>
using namespace std;
const int N = 1e3;
typedef long long ll;

ll f[N];

int main() {

  

  return 0;
}

这一讲我们来学习如何实现菲波那切数列，实现菲波那切数列不是什么难事，但是我们需要学会的是灵活使用。这一讲带大家计算第 n 个菲波那切数列的值。

这里我们先接收一个整数（这个整数不能太大，否则他可能超过long long，你可以在最后测试测试）。

请在main()函数中写下：

int n;

cin >> n;

 

这一步我们先初始化数据。

请在cin >> n;下面写下：

f[0] = f[1] = 1;

然后我们根据前面得出的通式f[n]=f[n−1]+f[n−2] 进行计算。这里我们要注意我们for循环的起始和结束，起始是从 2 开始的。因为我们在计算第 f[n] 的时候需要提前计算出 f[n−1] 和 f[n - 2]。所以这里的 n 做小是 2。因为我们需要计算的是 f[n] 。所以循环的结束是循环到 n 。

请在f[0] = f[1] = 1;下面写下：

1for (int i = 2; i <= n; ++i) {

2   f[i] = f[i - 1] + f[i - 2];

3}

这个时候我们就可以输出答案了。

请在return 0;上面写下：

1cout << f[n] << endl;

不知道你们有没有发现，其实我们是可以不用使用数组的。我们来进行一下空间优化。

我们先来初始化数据。

请在return 0;上面写下：

ll a = 1, b = 1, c = 1;

这一步我们和前面的一样，根据公式进行计算。但这里不同的是，我们需要更新 a, ba,b 的值。

请在return 0;上面写下：

for (int i = 2; i <= n; ++i) {
  	c = a + b;
    a = b;
  	b = c;
}

最后我们输出答案就可以了。

请在rerurn 0;上面写下：

cout << c << endl;

现在你可运行你的程序了。

可以查看第 10 个菲波那切数列的值。是不是和爬楼梯的答案一样？

当然如果你有精力，你也可以看看什么时候会出现溢出。

cout << c << endl;