_SGH_ @ 2024-12-01 09:46:39
记忆化的代码
include <bits/stdc++.h>
using namespace std;
long long shao[55];
long long ss(int m){
if(shao[m]!=0) return shao[m];
if(m == 1){
return 1;
}
if(m == 2){
return 2;
}
shao[m]= ss(m-1)+ss(m-2);
return shao[m];
}
int main(){
int n;
cin >> n;
cout << ss(n);
return 0;
} ``````
没记忆化的:
```cpp
#include <bits/stdc++.h>
using namespace std;
long long shao[55];
long long ss(int m){
if(m == 1){
return 1;
}
if(m == 2){
return 2;
}
return ss(m-1)+ss(m-2);
}
int main(){
int n;
cin >> n;
cout << ss(n);
return 0;
}
by niuniudundun @ 2024-12-01 09:53:55
@SGH数组开大点?
by niuniudundun @ 2024-12-01 09:55:08
@SGH用高精。
by shawn0618 @ 2024-12-01 09:57:58
不明白什么叫“输入数据记忆化”。
@SGH
by _SGH_ @ 2024-12-01 10:05:04
@niuniudundun没准备用高精呐,就是想试一下递归(学记忆化)
by _SGH_ @ 2024-12-01 10:22:32
@shawn0618大佬能不能解释一下
by shawn0618 @ 2024-12-01 10:31:33
如果是普通的记忆化的话。
把算过的记下来,可以节省重复算的时间。
正常的话可以拿60分。
by shawn0618 @ 2024-12-01 10:44:18
测过了没问题,不开高精是拿不到后面的40分的。
我们假设存在一个数组,下表从1开始,如果使用记忆化的话。 | 0 | 0 | 0 | 0 | 0 |
---|
假设要计算结果为5的答案,会递归
计算
计算 |
1 | 2 | 0 | 0 | 0 |
---|
接下来计算
以此类推,直到执行完栈。
数组变为: | 1 | 2 | 3 | 5 | 8 |
---|
执行到这一步时,访问
@SGH
by _SGH_ @ 2024-12-01 11:19:43
@shawn0618蟹蟹大佬,懂了!