nyoj 76-超级台阶 （递推）

76-超级台阶

内存限制:64MB
时间限制:1000ms
特判: No

通过数:8
提交数:12
难度:3

题目描述:

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

注：规定从一级到一级有0种走法。

输入描述:

输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40),  表示楼梯的级数。

输出描述:

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

样例输入:

复制

2

2

3

样例输出:

1

2

分析：
　　1、第m阶的走法应该是前面m-1阶的走法 + 前面m-2阶的走法；
　　2、m-1的走法就表示最后只走一个台阶，m-2的走法表示最后上两个台阶；
　　PS：所以我们可以类推，如果最初有三种走法即就是上1、2、3阶，那么当前的走法 = f[m-1] + f[m-2] + f[m-3].

核心代码：
　　

 for(int i = ; i <= MAXN; ++ i)

 {

     f[i] = f[i-] + f[i-];

 }

C/C++代码实现（AC）：

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 const int MAXN = ;

 int f[MAXN] = {, , , };

 void cal_excel()

 {

     for(int i = ; i < MAXN; ++ i)

         f[i] = f[i-] + f[i-];

 }

 int main()

 {

     int t;

     cal_excel();

     scanf("%d", &t);

     while(t --)

     {

         int m;

         scanf("%d", &m);

         printf("%d\n", f[m]);

     }

     return ;

 }