简单斐波那契（递归实现）
题目 简单斐波那契
思路分析
普通的递归会tle
可以发现很多值在左边已经提前算过 而右边又重新算一遍
所以可以把值保存在记忆化数组里面 再右边又碰到相同参数时
无需再做递归 只要取出答案即可
这是递归+记忆化数组的第一次接触 后面会用这个引入dp问题
代码实现
tle
#include<bits/stdc++.h>
using namespace std;
int N;
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
cout << fibonacci(i);
if (i < N - 1)
cout << " ";
}
return 0;
}
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
int N;
// 记忆化数组
vector<int> memo(50, -1);
int fibonacci(int n) {
// 基本情况
if (n <= 1)
return n;
// 如果已经计算过这个值，则直接返回结果
if (memo[n] != -1)
return memo[n];
// 否则，递归计算，并保存结果
memo[n] = fibonacci(n-1) + fibonacci(n-2);
return memo[n];
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
cout << fibonacci(i);
if (i < N-1)
cout << " ";
}
return 0;
}
💬 评论