HDU 2041 超级楼梯

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

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

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

Sample Input

2 2 3

Sample Output

1 2

java code

简单递推
逆向思考，最后一级只能是m-1步或是m-2步
总的走法就是m-1的走法加上m-2的走法，即最后一级的前一级的走法
递推公式就是F(n) = F(n-1) + F(n-2)
令F(1) = 1 , F(2) = 2

也就是斐波拉基递推
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        for (int j = 0; j < n; j++) {
            int m = cin.nextInt();
            int a[] = new int[45];
            for (int i = 2; i <= m; i++) {
                a[2] = 1;
                a[3] = 2;
                if (i > 3)
                    a[i] = a[i - 1] + a[i - 2];
            }
            System.out.println(a[m]);
        }
        cin.close();
    }

}```