优化的idea:
用了闫总视频里面提到的preprocessing方法，用一个HashMap去存能合法转移到当前状态的其他状态，节省一些计算时间

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while(true) {
            //read input
            int n = sc.nextInt();
            int m = sc.nextInt();
            if(n == 0 && m == 0) break;
            int numbers = 1 << n;     //number of states
            boolean[] states = new boolean[numbers + 1];
            Map<Integer, List<Integer>> validTransform = new HashMap<>();
            long[][] dp = new long[m + 1][numbers];
            //check if each state is valid
            for(int i = 0; i < numbers; i++) {
                //count how many 0 before the current digit
                int count = 0;
                boolean isValid = true;
                //starting from the first digit to the last digit
                for(int j = 0; j < n; j++) {
                    //if the digit is 1
                    if(((i >> j) & 1) == 1) {
                        //if has odd numbers of 0 before
                        if((count & 1) == 1) {
                            isValid = false;
                            break;
                        }
                        else {
                            count = 0;
                        }
                    } else {
                        count++;
                    }
                }
                //check if it has odd 0s at the begining
                if((count & 1) == 1) isValid = false;
                states[i] = isValid;
            }

            //对于每一个状态而言，枚举所有可以转移到这个状态的合法状态
            for(int i = 0; i < numbers; i++) {
                for(int j = 0; j < numbers; j++) {
                    //check if it overlaps or is valid when they do an or operation
                    if((i & j) == 0 && states[i | j]) {
                        List<Integer> list = validTransform.getOrDefault(i, new ArrayList<Integer>());
                        list.add(j);
                        validTransform.put(i, list);
                    }
                }
            }


            //initialize
            dp[0][0] = 1;

            for(int i = 1; i<= m; i++) {
                for(int j = 0; j < numbers; j++) {
                    List<Integer> validStates = validTransform.get(j);
                    //find the valid transfroms and add them all
                    for(int eachState: validStates) {
                        dp[i][j] += dp[i - 1][eachState];
                    }
                }
            }
            System.out.println(dp[m][0]);
        }
    }
}