openjudge 菲波那契数列 2753

2018-3-15

斐波那契数列 这个对我们来说应该并不陌生，f(n)=f(n-1)+f(n-2)，初始化f(1)=1，f(2)=1，当n比较大的时候，我们会发现有些f(m)会被我们计算了多次，那么我们可以先将它们存到数组里，如果我们需要用的话直接去数组里面取就可以了。

#include<iostream> #include<cstring> using namespace std; const int N = 20; int fib[N+1]; int dfs(int p){ if (fib[p]) return fib[p]; fib[p]=dfs(p-1)+dfs(p-2); return fib[p]; } int main(){ memset(fib,0,sizeof(fib)); fib[1]=1;fib[2]=1; int t,n; cin>>t; while(t--){ cin>>n; if (fib[n]) cout<<fib[n]<<endl; else cout<<dfs(n)<<endl; } return 0; }