algorithmzuo / algorithmbasic2020 Goto Github PK

        public static long ways3(int N, int M) {
		if (N < 1 || M < 1 || ((N * M) & 1) != 0) {
			return 0;
		}
		if (N == 1 || M == 1) {
			return 1;
		}
		int max = Math.max(N, M);
		int min = Math.min(N, M);
		int pre = (1 << min) - 1;
		long[][] dp = new long[1 << min][max + 1];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][j] = -1;
			}
		}
		return process3(pre, 0, max, min, dp);
	}

	public static long process3(int pre, int i, int N, int M, long[][] dp) {
		if (dp[pre][i] != -1) {
			return dp[pre][i];
		}
		long ans = 0;
		if (i == N) {
			ans = pre == ((1 << M) - 1) ? 1 : 0;
		} else {
			int op = ((~pre) & ((1 << M) - 1));
			ans = dfs3(op, M - 1, i, N, M, dp);
		}
		dp[pre][i] = ans;
		return ans;
	}

	public static long dfs3(int op, int col, int level, int N, int M, long[][] dp) {
		if (col == -1) {
			return process3(op, level + 1, N, M, dp);
		}
		long ans = 0;
		ans += dfs3(op, col - 1, level, N, M, dp);
		if (col > 0 && (op & (3 << (col - 1))) == 0) {
			ans += dfs3((op | (3 << (col - 1))), col - 2, level, N, M, dp);
		}
		return ans;
	}