# What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?

On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem:

You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. Find the maximum number of dominoes you can place on the board so that each domino covers exactly 2 squares and no dominoes overlap.

I solved it quite easily: the solution is just floor(M*N/2).

I read that in order for a problem to be solved Greedily, it needs to have "optimal substructures". For this problem, what were the "optimal substructures"?

Thank you in advance.

I think there's a slight misunderstanding in the question. The phrase is "optimal substructure", not "optimal substructures". It's not a matter of looking at the individual substructures (e.g., regions of the grid you're trying to tile) and saying, "This one's optimal", "This one's optimal", "This one isn't". Rather, it's a matter of looking at the structure and interactions of the subproblems and saying, "The substructures of this problem (i.e., the subproblems) interact in a way that lets me find an optimal solution easily."

I also don't think this is a great example for greedy algorithms, since greedy algorithms are naturally somewhat recursive and it's so easy to domino-tile a grid iteratively that it feels artificial to force it into a recursive solution. But here goes...

One example of optimal substructure is that, if you can divide your grid into rectangles $A$ and $B$ and you can perfectly tile $A$, then an optimal tiling of the whole grid can be made from the perfect tiling of $A$ along with an optimal tiling of $B$. This gives the following greedy algorithm.

function tile (int width, int height, int startrow)
if (startrow <= height-1)
perfectly tile rows startrow and startrow+1 like this | | ... |
tile (width, height, startrow+2)
else if (startrow == height) then
tile the last row like this -- -- ... -- , with one empty square
at the end if width is odd
/* else startrow > height and there's nothing to do */


Note that this just produces tilings like this one for a $7\times3$ grid,

| | | | | | |
| | | | | | |
--- --- ---


which is exactly what you'd do iteratively.