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

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

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

Sample Input
2
2
3

Sample Output
1
2

解题思路:

首先从题意分析,每一次有两种走法,第一种是走一个台阶,第二种是走两个台阶,我们从后往前看,如果它走到了第i级台阶,那么它的上一次走法有几种呢?显然是两种,从i-1级台阶或者i-2级台阶走到i级台阶。所以通过上述分析,设走到第i级台阶有f[i]总走法,那么f[i]=f[i-1]+f[i-2]也就是从到第i-1的走法,加上到i-2的走法之和。我们还可以得出f[1]=0,f[2]=1,f[3]=2,我在解释一下这三个数据,首先第一级就是开始站的位置,所以需要0步,第二级只能从第一级走一步达到,所以f[2]=1,第三级可以从第一级走两步,或者第二级走一步,(注意为什么不是从第一级走到第二级,在从第二级走到第三级呢?)因为从第二级走到第三级已经包括这种情况,所以不必考虑!

代码:

#include <iostream>
using namespace std;
int f[43];
 
int main()
{
	int n,m,i;
	f[1]=0;
	f[2]=1;
	f[3]=2;
	
	for(i=4;i<=42;++i)
		f[i]=f[i-1]+f[i-2];
	cin>>n;
	while(n--)
	{
		cin>>m;
		cout<<f[m]<<endl;
	}
	return 0;
} 

总结:
这道题主要考的是递推,和斐波那契数列,二者也都属于动态规划(DP)中初级知识,动态规划的本质就是,记录正确答案,以及两个性质,无后效性,最优子结构!