ACM | Super Staircase
有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法?
输入格式:
输入数据首先包含一个整数N,表示测试实例的个数,然后是N行数据,每行包含一个整数M(1<=M<=40),表示楼梯的级数。
输出格式:
对于每个测试实例,请输出不同走法的数量
输入样例:
2 2 3 # 输出样例: 1 2
代码示例1:
递归超时 #include<stdio.h>
int stairs(int n){
if(n==2) return 1;
if(n==3) return 2;
return stairs(n-1)+stairs(n-2);
}
int main(){
int N,M;
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d",&M);
printf("%d\n",stairs(M));
}
return 0;
}
代码示例2:
解析法/动态规划 其实还可以用记忆化搜索(缓存之前计算的结果)
#include<stdio.h>
int main(){
int N,M;
scanf("%d",&N);
int mem[50];
mem[1]=0;
mem[2]=1;
mem[3]=2;
for(int i=0;i<N;i++){
scanf("%d",&M);
for(int i=4;i<=M;i++){
mem[i]=mem[i-1]+mem[i-2];
}
printf("%d\n",mem[M]);
}
return 0;
}