ac君，可以采用记忆化方式：
```cpp
#include<bits/stdc++.h>
using namespace std;
long long s[105]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,1548008755920};
int main() {
    int n;
    cin>>n;
    cout<<s[n-1];
    return 0;
}
```


采用递归，$dfs(x)$ 的返回值是第 $x$ 项斐波那契数列的值，则输出 $dfs(n)$,递归的终止条件可以是当 $x=1$ 或 $x=2$ 时，返回 $1$。单纯的递归会超时，可以采用记忆化，用数组存储答案。
```cpp
#include <iostream>
using namespace std;

long long f[69];
long long dfs(int x) {
	if (f[x]) {
		return f[x];
	}
	if (x <= 2) {
		return f[x] = 1;
	}
	return f[x] = dfs(x - 1) + dfs(x - 2);
}
int main() {
	int n;
	cin >> n;
	cout << dfs(n);
    return 0;
}
```


斐波那契记忆化

采用递归

管理员

采用递归，dfs(x)dfs(x)dfs(x) 的返回值是第 xxx 项斐波那契数列的值，则输出 dfs(n)dfs(n)dfs(n),递归的终止条件可以是当 x=1x=1x=1 或 x=2x=2x=2 时，返回 111。单纯的递归会超时，

全部评论 1