``` #include<bits/stdc++.h> using namespace std; int dp[45]; int m; // m 级楼梯 int n; // 测试数据的个数 // 初始化dp数组，计算1-40级台阶 void InitDp() { dp[1] = 1; // 走上一级台阶只有一种走法 dp[2] = 2; // 走上两级台阶只有两种走法 // 后面的台阶既有可能是跨一级到的，也有可能是通过跨两级到的。因此状态转移方程是a[m]=a[m-1]+a[m-2] for(int i = 3; i <= 40; i++) { dp[i] = dp[i-1]+dp[i-2]; } } int main() { InitDp(); cin >> n; while(n--) { cin >> m; cout << dp[m-1] << endl; // 题上说的是走上m级,所以要走的有m-1级 } return 0; } ```

```cpp // https://dashoj.com/p/129 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; while (n--) { int m; cin >> m; vector<int> dp(m + 7, 0); dp[1] = 1, dp[2] = 1; for (int i = 4; i <= m; i++) dp[i] += dp[i - 1] + dp[i - 2]; cout << dp[m] << endl; } return 0; } ```

``` import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); //次数为n int[] m=new int[n]; for (int i = 0; i < n; i++) { m[i]=sc.nextInt()-1; } int[][] dp=new int [n][45]; for (int i = 0; i < n; i++) { dp[i][0]=1; dp[i][1]=1; dp[i][2]=2; } for (int i = 0; i < n; i++) { //次数 for (int j = 2; j <= m[i]; j++) { // dp[i][j]=dp[i][j-1]+dp[i][j-2]; } } for (int i = 0; i < n; i++) { System.out.println(dp[i][m[i]]); } } } ```

include include using namespace std; int main() { int n; cin >> n; vector su(n+1); for (int i = 1; i > su[i]; int way[1001]; way[1] = 0; way[2] = 1; way[3] = 2; for (int i = 1; i <= n; i++) { for (int j = 4; j <= su[i]; j++) way[j] = way[j - 1] + way[j - 2]; cout << way[su[i]] << endl; } ``` return 0; ``` }

``` #include <bits/stdc++.h> using namespace std; int dp[N]={0}; signed main(){ int count; dp[1]=1; dp[2]=1; cin>>count; for(int i=3;i<51;i++){ dp[i]=dp[i-1]+dp[i-2]; } for(int i=0;i<count;i++){ int x; cin>>x; cout<<dp[x]<<endl; } return 0; } ```

``` for i in range(int(input())): m = int(input()) dp = [0]*50 dp[1] =1 dp[2] =1 for i in range(3,45): dp[i] = dp[i-1]+dp[i-2] print(dp[m]) ```