TopCoder FourBlocks problem

The code below is an answer to a popular topcoder problem FourBlocks(You need to log in). The solution uses bitmask memoization to find the max sum in the grid using blocks of size 1 and a square block of size 4. Can anybody help me in understanding how it works? What does this do

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

Also how does function rec() fit in a square?? its only comparing 2 bits.

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);
    }
  }


}开发者_StackOverflow社区

The 1<<n is the number of ways to fill a row with 1's. (1<<n = 2^n). It looks like he calculates all possible ways to fill the board with 1, and then checks how many fours to fit in. To speed it up, he uses dynamic programming, to collapse it from being exponential in the number of rows.