This task is a classic example of dynamic programming.

Let the state be a function which maps some form of the board with potentially occupied fields in the last row and the number of dominoes into the best coverage we can possibly get. More specifically, we want to know the best coverage for every number of rows ~N~, number of dominoes ~K~ and a set of occupied fields in the last row ~B~.

The solution for a certain state can be calculated based on previous states so that we try to place dominoes in the last row in every ~11~ ways possible. Each of these ways is going to need some available fields in the previous row and will occupy some fields in the current row. The ways are represented in a bitmask where the first digit is the binary code of the place we're occupying in the previous row and the second digit is the binary code of the place we're occupying in the current row.

const mask_t cases[11] = {
    0x00,                           // without domino placed
    0x11, 0x22, 0x44, 0x03, 0x06,   // if we place 1 domino
    0x17, 0x47, 0x33, 0x55, 0x66    // if we place 2 dominoes
};

Using these moves, we can construct a relation. The number of states is ~8 \times N \times K = 8\,000\,000~, whereas the relation in our example is a constant, ~11~. The memory usage is exactly ~8 \times 1000 \times 1000~ long long types of data. This is 64 MB.

There is a solution which uses only 32 MB.