Problem Description
有一樓梯共M級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？

Input
輸入數(shù)據(jù)首先包含一個整數(shù)N，表示測試實例的個數(shù)，然后是N行數(shù)據(jù)，每行包含一個整數(shù)M（1<=M<=40）,表示樓梯的級數(shù)。

Output
對于每個測試實例，請輸出不同走法的數(shù)量

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();
    }

}```