你的解法是 $O(1.618^n)$ 的，通过不了。你应该使用一个数组，在得到答案时立即存储，下次递归到这时不用再递归下去，直接查询即可。

```cpp
#include <iostream>
#include <cstdio>
using namespace std;
long long f[65];
long long fib(int n){
	if(n == 1 || n == 2) return 1;
	if(f[n]) return f[n];
	f[n] = fib(n - 1) + fib(n - 2);
	return f[n];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	cout << fib(n);
	
	return 0;
}
```

CSP-J一等奖

出题人


```cpp
#include<bits/stdc++.h>
using namespace std;
int dfs(int n){
    if(n == 1 || n == 2) return 1;    //终止条件
    return dfs(n-1) + dfs(n-2);    //递归式
}
int main(){
    int n;
    cin >> n;
    cout << dfs(n);
    return 0;
}
```


斐波那契记忆化

为什么TLE，哪位大佬帮帮忙

题目的执行用时击败了99%的用户

时间刺客

题目的内存消耗击败了99%的用户

空间掌握者

2025年7月的累计刷题天数达到20天

全部评论 1