HDU 2041 超级楼梯

解题报告：

题目大意：现要跨上一个结束为M 的台阶，每次可以选择一次跨一级台阶或者一次跨上两级台阶，问跨上这个M级的台阶有多少种跨法。

最简单的动态规划题，假设我现在在第n级台阶上，要跨上级数为M的台阶可以将问题转化为要从第n 级台阶一步跨只跨一级台阶跨到n+1级台阶上，也可以选着一次一步跨两级台阶直接跨到n+2级台阶上，所以从第n级台阶跨上M级台阶的方法种数就是从第n级台阶一步跨一级跟一步跨两级的和就为从第n级台阶跨上M级台阶的方法种数。

View Code

 1 #include<stdio.h>
 2 int DP[45];
 3 void dabiao(void) {
 4     DP[1]=0;
 5     DP[2]=1;
 6     DP[3]=2;
 7     for(int i=4;i<=41;++i)
 8     DP[i]=DP[i-1]+DP[i-2];
 9 }
10 int main() {
11     int T,M;
12     dabiao();
13     scanf("%d",&T);
14     while(T--) {
15         scanf("%d",&M);
16         printf("%d\n",DP[M]);
17     }
18     return 0;
19 }