采用递归
2024-03-21 16:21:55
发布于:浙江
28阅读
0回复
0点赞
采用递归, 的返回值是第 项斐波那契数列的值,则输出 ,递归的终止条件可以是当 或 时,返回 。单纯的递归会超时,可以采用记忆化,用数组存储答案。
#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;
}
这里空空如也
有帮助,赞一个