ACM的一道问题。。。

典型的斐波那契数列，有2中方法。
迭代：
#include
using std::cin;using std::cout;
using std::endl;

int main(){
int n(0), m(0);
cin>>n;
while(n>0)
{
int feb[2]={1,1};
cin>>m;
if(2==m)cout<<1< else if(m>2)
{
for(int i(2);i {
int tmp(feb[1]);
feb[1]+=feb[0];
feb[0]=tmp;
}
cout< }
--n;
}
}

递归：
#include
using std::cin;using std::cout;
using std::endl;

int feb(const int &n)
{
if(2==n||1==n)return 1;
else if(n>2)
{
return feb(n-1)+feb(n-2);
}
return 0;
}
int main()
{
int n(0), m(0);
cin>>n;
while(n>0)
{
cin>>m;
cout< --n;
}
return 0;
}

很简单的动态规划。
dp[i]表示第i个站有多少种方案。
则有：
dp[1]=dp[2]=1;
dp[i]=dp[i-1]+dp[i-2];
以此类推