TopCoder FourBlocks問題

Question

下面的代碼是一個流行的topcoder問題的答案FourBlocks（您需要登錄）。該解決方案使用位掩碼記憶法，使用大小爲1的塊和大小爲4的方塊查找網格中的最大和。任何人都可以幫助我理解它的工作原理嗎？這是幹什麼的

int[][] d = new int[m + 1][1 << n] // why 1<<n ? 

又如何函數rec（）適合在廣場？其唯一的比較2位。

import java.util.*; 
import java.util.regex.*; 
import java.text.*; 
import java.math.*; 


public class FourBlocks 
{ 
    int n; 

    public int maxScore(String[] grid) 
    { 
    n = grid.length; 
    int m = grid[0].length(); 
    int[][] d = new int[m + 1][1 << n]; 
    int ans = 0; 
    for (int i = 0; i < m; ++i) { 
     int mask = 0; 
     for (int j = 0; j < n; ++j) { 
     if (grid[j].charAt(i) == '1') { 
      mask |= 1 << j; 
     } 
     } 
     ans += Integer.bitCount(mask); 
     for (int j = 0; j < 1 << n; ++j) { 
     if ((j & mask) == 0) { 
      rec(0, j | mask, 0, d[i][j], d[i + 1]); 
     } 
     } 
    } 
    return d[m][0] + ans; 
    } 

    void rec(int i, int mask, int mask2, int sum, int[] d) { 
    if (i == n) { 
     d[mask2] = Math.max(d[mask2], sum); 
     return; 
    } 
    rec(i + 1, mask, mask2, sum, d); 
    if ((mask & (1 << i)) == 0) { 
     rec(i + 1, mask, mask2, sum + 1, d); 
    } 
    if (i < n - 1 && (mask & (1 << i)) == 0 && (mask & (1 << (i + 1))) == 0) { 
     rec(i + 2, mask, mask2 | (1 << i) | (1 << (i + 1)), sum + 16, d); 
    } 
    } 


} 

Answer 1

的1<<n是想方設法填滿一排1的數量。 （1<<n = 2^n）。 看起來他計算了所有可能的方法來填充棋盤1，然後檢查要裝入多少四肢。爲了加快速度，他使用動態編程來將它從行數的指數中摺疊掉。