没毛病，100%正确

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int L = sc.nextInt();

        while (L-- > 0) {

            int N = sc.nextInt();

            int M = sc.nextInt();

            if (N < M) {

                System.out.println(1 << N);

                continue;

            }

            int fullMask = (1 << M) - 1;

            long[][] dp = new long[N + 1][1 << M];

            dp[0][0] = 1;

            for (int i = 0; i < N; i++) {

                for (int mask = 0; mask < (1 << M); mask++) {

                    if (dp[i][mask] == 0) continue;

                    // 放 0

                    int newMask = ((mask << 1) & fullMask);

                    dp[i + 1][newMask] += dp[i][mask];

                    // 放 1

                    newMask = ((mask << 1) & fullMask) | 1;

                    if (newMask != fullMask) { // 不能连续 M 个 1

                        dp[i + 1][newMask] += dp[i][mask];

                    }

                }

            }

            long total = 0;

            for (int mask = 0; mask < (1 << M); mask++) {

                total += dp[N][mask];

            }

            System.out.println(total);

        }

        sc.close();

    }

}