采用递归

AC君

2024-03-21 16:21:55

发布于：浙江

104阅读

0回复

0点赞

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

#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;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

ac君，可以采用记忆化方式：

#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;
}

2024-08-05 来自北京

人
回复AC
6

2024-09-04 来自浙江
0
北辞
回复AC
《记忆化》

2024-10-05 来自广东
0