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

解题思路:用dp[i]表示走到第i级的方法数。
              那么走到第i级的最后一步只可能是两种,走一级或者两级,即dp[i]=dp[i-1]+dp[i-2]
             
              注意,开始的时候是在第一级开始的,所以要求的是dp[n-1]
 
              写完之后才发现它是斐波那契数列啊~~囧~!!!

代码:

 

 1#include <iostream>
 2#include <cstdio>
 3#include <cmath>
 4
 5using namespace std;
 6
 7long long sum[45];
 8int T,n;
 9
10int main()
11{   sum[1]=1;
12    sum[2]=2;
13    for (int i=3; i<=40; i++)
14      sum[i]=sum[i-1]+sum[i-2];
15    cin >> T;
16    while (T--)
17    {  cin >> n;
18       cout << sum[n-1<< endl;
19    }

20    return 0;
21}

22