DominoFill.java

package Dynamic_Programming;
public class DominoFill {

	/**
	 * .....
	 * ..234
	 * 01
	 */
	public static int method1(int R, int C) {
		int[] prev = new int[1 << C];
		prev[(1 << C) - 1] = 1;

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				int[] cur = new int[1 << C];
				for (int mask = 0; mask < 1 << C; mask++) {
					if ((mask & (1 << c)) != 0) {
						cur[mask ^ (1 << c)] += prev[mask]; // do nothing

						if (c > 0 && (mask & (1 << (c - 1))) == 0) {
							cur[mask | (1 << (c - 1))] += prev[mask]; // horizontal
						}
					} else {
						cur[mask | (1 << c)] += prev[mask];  // vertical
					}
				}
				prev = cur;
			}
		}

		return prev[(1 << C) - 1];
	}

	/**
	 * .....
	 * ..012
	 * 34
	 */
	public static int method2(int R, int C) {
		int[] prev = new int[1 << C];
		prev[(1 << C) - 1] = 1;

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				int[] cur = new int[1 << C];
				for (int mask = 0; mask < 1 << C; mask++) {
					int nmask = (mask << 1) & ((1 << C) - 1);
					if ((mask & (1 << (C - 1))) != 0) {
						cur[nmask] += prev[mask]; // do nothing

						if (c > 0 && ((mask & 1) == 0)) {
							cur[nmask | 3] += prev[mask]; // horizontal
						}
					} else {
						cur[nmask | 1] += prev[mask]; // vertical
					}
				}
				prev = cur;
			}
		}

		return prev[(1 << C) - 1];
	}

	// random test
	public static void main(String[] args) {
		for (int r = 1; r < 10; r++) {
			for (int c = 1; c < 10; c++) {
				int res1 = method1(r, c);
				int res2 = method2(r, c);
				if (res1 != res2)
					throw new RuntimeException();
			}
		}
	}

	public static int method0(int R, int C) {
		int[][][] dp = new int[R + 1][C][1 << C];
		dp[0][C - 1][(1 << C) - 1] = 1;

		for (int r = 1; r <= R; r++) {
			for (int c = 0; c < C; c++) {
				int[] prev = c > 0 ? dp[r][c - 1] : dp[r - 1][C - 1];
				for (int mask = 0; mask < 1 << C; mask++) {
					if ((mask & (1 << c)) != 0) {
						dp[r][c][mask ^ (1 << c)] += prev[mask]; // do nothing

						if (c > 0 && (mask & (1 << (c - 1))) == 0) {
							dp[r][c][mask | (1 << (c - 1))] += prev[mask]; // horizontal
						}
					} else {
						dp[r][c][mask | (1 << c)] += prev[mask];  // vertical
					}
				}
			}
		}

		return dp[R][C - 1][(1 << C) - 1];
	}
}