[数据结构与算法]2021新生赛热身赛简述

1.走楼梯
时间限制: C/C++ 1000ms; Java 2000ms 内存限制: 65535KB
通过次数: 34 总提交次数: 94

问题描述
有一楼梯共M级，刚开始时你在第零级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

输入描述
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

输出描述
对于每个测试实例，请输出不同走法的数量

样例输入
2
3
4
样例输出
3
5

#include<stdio.h>
int count=0,m;
int main(){
	int n;
	scanf("%d",&n);
	bool dfs(int i); 
	for(int i=0;i<n;i++){
		count=0;
		scanf("%d",&m);
		dfs(0);//深度优先搜索
		printf("%d\n",count);
	}
	return 0;
}
bool dfs(int i){
	if(i==m) count++;
	if(i>m) return 0;
	dfs(i+1);//每次走一步
	dfs(i+2);//或走两步
}

注意：这个会超时，m=40时，2的40很大。
观察规律，这是一个斐波那契数列。

#include<stdio.h>
int main(){
	int n,m;
	int fb(int i);
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&m);
		printf("%d\n",fb(m));
	}
	return 0;
}
int fb(int i){
	if(i==1) return 1;
	else if(i==2) return 2;
	else return fb(i-1)+fb(i-2);
}

在比赛中学会寻找规律，优化算法，是我们acm实验室成员必不可少的技能。