Given a rectangle consisting of 1's and 0's, how can I find the maximum number of non-overlapping 2x2 squares of 1's?

Example:

```
0110
1111
1111 

```

The solution would be 2.

I know it can be solved with Bitmask DP; but I can't really grasp it - after playing with it for hours. How does it work and how can it be formalised?
['https://Stackoverflow.com/questions/28071829', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1327559/']
I wanted to point out that the graph we get by putting vertices at the centers of squares and joining them when they overlap is *not* claw-free:

If we take (in the full plane) a 2x2 square and three of the four diagonally overlapping 2x2 squares, they form the induced subgraph

```
•   •
 \ /
  •
 /
•

```

This is a claw, meaning that any region containing those squares corresponds to a non-claw-free graph.
Here is a dynamic programming solution.

1. The state is `(row number, mask of occupied cells, shift position)`. It looks like this:

```
..#..    
.##..  
.#...  
.#...  

```

In this case, the row number is 2(I use zero-bases indices), the mask depends on whether we take a cell with `#` or not, the shift position is 1. The number of states is `O(n * m * 2 ^ n)`. The value of a state is the maximum number of picked 2x2 squares. The base case is `f(1, 0, 0) = 0`(it corresponds to the first row and no 2x2 squares picked so far).
2. The transitions are as follows:

```
..#..    ..#..
.00.. -> ..1..
.0...    .11..
.#...    .#...

```

This one can be used if and only if the square consists of ones in the original matrix and there were zeros in the mask(it means that we pick this square).
The other one is:

```
..#..    ..#.. 
.##.. -> ..#..
.#...    .#0..
.#...    .#...

```

This one is always applicable. It means that we do pick this 2x2 square.
When we are done with one row, we can proceed to the next one:

```
..#..    ..#0.
..#.. -> ..#..
..#..    ..#..
.##..    ..#..

```

There are at most two transitions from each state, so the total time complexity is `O(n * m * 2 ^ n)`. The answer the maximum among all masks and shifts for the last row.