Choose max number of non-overlapping 2x2 squares in binary bitmap

Question

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?

Answer 1

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.