#include<bits/stdc++.h> #define ll long long using namespace std; ll a[100005]; int main(){ ll n; cin >> n; a[0] = 0; a[1] = 1; a[2] = 2; for(int i = 3;i <= n;i++) a[i] = a[i-1] + a[i-2]; cout << a[n]; return 0; }

题解

CP003068 递推题解 这是经典的递推题，测试数据很大，递归会超时。 递归代码（测试点10超2）： 递推代码（AC）：

必看！

#include<bits/stdc++.h> using namespace std; #define ll long long ll ac[6000]; int main(){ long long n; cin>>n; ac[1]=1;//一步有一种方法 ac[2]=2;//两步有两种方法 ac[3]=3;//三步有三种方法 for(int i=4;i<=n;i++)ac[i]=ac[i-1]+ac[i-2];//直接套用斐波那契数列公式 cout<<ac[n]<<"\n";//输出 return 0; }

就一个上楼梯而已.

金典递推

#include <bits/stdc++.h> using namespace std; long long k[1000010]={1,2}; int main(){ int n; cin>>n; for(int i=2;i<n;i++){ k[i]=k[i-1]+k[i-2]; } cout<<k[n-1]; return 0; }

加粗文本

#include <bits/stdc++.h> using namespace std; long long n,f[100005]; int main(){ cin>>n; f[1]=1; f[2]=2; for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]; cout<<f[n]; return 0; }

翻版兔子数列

#include<bits/stdc++.h> using namespace std; int main(){ long long k[100005],n; cin >> n; k[1]=1; k[2]=2; for(int i=3;i<=n;i++){ k[i]=k[i-1]+k[i-2]; } cout << k[n]; }

#include<bits/stdc++.h> using namespace std; long long a[10000] ={0,1,2,0},n; int main(){ cin>>n; for( int i =3;i<= 100;i++){ a[i] =a[i-1] + a[i-2]; } cout<<a[n]; }