天天看點

動态規劃-狀态壓縮-覆寫

2020-03-01 23:08:51

問題描述:

你有一塊棋盤,棋盤上有一些格子已經壞掉了。你還有無窮塊大小為1 * 2的多米諾骨牌,你想把這些骨牌不重疊地覆寫在完好的格子上,請找出你最多能在棋盤上放多少塊骨牌?這些骨牌可以橫着或者豎着放。

輸入:n, m代表棋盤的大小;broken是一個b * 2的二維數組,其中每個元素代表棋盤上每一個壞掉的格子的位置。

輸出:一個整數,代表最多能在棋盤上放的骨牌數。

示例 1:

動态規劃-狀态壓縮-覆寫

輸入:n = 2, m = 3, broken = [[1, 0], [1, 1]]

輸出:2

解釋:我們最多可以放兩塊骨牌:[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。

示例 2:

動态規劃-狀态壓縮-覆寫

輸入:n = 3, m = 3, broken = []

輸出:4

解釋:下圖是其中一種可行的擺放方式

限制:

1 <= n <= 8

1 <= m <= 8

0 <= b <= n * m

問題求解:

public int domino(int m, int n, int[][] broken) {
        int[][] dp = new int[m + 1][1 << n];
        int[][] board = new int[m][n];
        for (int[] b : broken) board[b[0]][b[1]] = 1;
        int[] states = new int[m + 1];
        states[0] = (1 << n) - 1;
        for (int i = 1; i <= m; i++) {
            int state = 0;
            for (int j = 0; j < n; j++) {
                if (board[i - 1][j] == 1) state |= (1 << (n - 1 - j));
            }
            states[i] = state;
        }
        for (int i = 1; i <= m; i++) {
            for (int u = 0; u < 1 << n; u++) {
                if ((u & states[i - 1]) != 0) continue;
                int prev = u | states[i - 1];
                for (int v = 0; v < 1 << n; v++) {
                    if ((v & states[i]) != 0) continue;
                    // 枚舉豎放的位置
                    for (int k = v;; k = (k - 1) & v) {
                        if ((k & prev) == 0) {
                            dp[i][v] = Math.max(dp[i][v], calc_1(k) + calc_2(v ^ k) + dp[i - 1][u]);
                        }
                        if (k == 0) break;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 1 << n; i++) res = Math.max(res, dp[m][i]);
        return res;
    }
    
    private int calc_1(int num) {
        int res = 0;
        for (int i = 0; i < 32; i++) if ((num & (1 << i)) != 0) res += 1;
        return res;
    }
    
    private int calc_2(int num) {
        int res = 0;
        for (int i = 0; i < 32;) {
            if ((num & (1 << i)) != 0 && i + 1 < 32 && (num & (1 << (i + 1))) != 0) {
                res += 1;
                i += 2;
            }
            else {
                i += 1;
            }
        }
        return res;
    }