算法与数据结构 | 您所在的位置:网站首页 › 计算斐波那契数列的第n项递归和非递归算法 › 算法与数据结构 |
算法与数据结构---6.6、斐波那契数列-记忆化递归 一、总结 一句话总结: 记忆化递归,就是把已经计算的中间状态保存下来,下次需要的时候就直接拿这个结果,就避免了递归中的重复计算中间状态 #include #include using namespace std; const int mod=1000000007; int cache[200000]; int find(int n){ //就是如果缓存中有,就直接拿缓存 //否则计算,然后将计算的结果保存到缓存 if(cache[n]!=-1) return cache[n]; else{ return cache[n]=(find(n-1)+find(n-2))%mod; } } int main(){ int n; cin>>n; memset(cache,-1,sizeof(cache)); cache[2]=cache[1]=1; cout |
CopyRight 2018-2019 实验室设备网 版权所有 |