超级楼梯 Time Limit: / MS (Java/Others) Memory Limit: / K (Java/Others)
Total Submission(s): Accepted Submission(s): Problem Description
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ Input
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（<=M<=）,表示楼梯的级数。 Output
对于每个测试实例，请输出不同走法的数量 Sample Input Sample Output Author
lcy Source
2005实验班短学期考试
Recommend
lcy
水题，递归。
很有意思的一道递归题，用普通的递归会超时，需要改用记忆递归法。记忆递归法，牺牲空间来换取时间，可以采用数组（数组空间浪费大，但是读取速度快）。
code：
Problem : ( 超级楼梯 ) Judge Status : Accepted
RunId : Language : G++ Author : freecode
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta #include <iostream>
using namespace std; /* 用普通递归会超时，改用记忆递归法（将数据存储在数组里）
int m; int f(int n)
{
if(n>m)
return 0;
else if(n==m)
return 1;
else
return f(n+1)+f(n+2);
}
*/ int main()
{
/*
int T;
cin>>T;
while(T--){
cin>>m;
cout<<f(1)<<endl;
}
*/ int a[];
a[]=,a[]=; for(int i=;i<=;i++) //记忆递归法。牺牲空间，换取时间。
a[i]=a[i-]+a[i-]; int T,m;
cin>>T;
while(T--){
cin>>m;
cout<<a[m]<<endl;
}
return ;
}
第二次做。
水题。
常规做法会超时，输出几组连续的测试数据会发现，输出结果是斐波那契数列。那么题目就简单了，直接构造一个40以内的斐波那契数列即可，f1=1，f2=1。
常规做法是写一个递归，作用是记录当前走到了哪一级阶梯（假设为n），所以出口是当n>M（直接return;）或者n==M（sum++;return ;），递归体是f(n+1)然后f(n+2)，分别表示当前走1级阶梯和2级阶梯的情况。
代码：
1 #include <iostream>
2
3 using namespace std;
4 int sum;
5 int m;
6 int a[41];
7 void f()
8 {
9 a[1] = 1;
10 a[2] = 1;
11 for(int i=3;i<=40;i++)
12 a[i] = a[i-1] + a[i-2];
13 }
14 int main()
15 {
16 int n;
17 f();
18 cin>>n;
19 while(n--){
20 cin>>m;
21 cout<<a[m]<<endl;
22 }
23 return 0;
24 }
Freecode : www.cnblogs.com/yym2013