Tray Bien

This problem asks us to fill a 3-by-x foot space with trays of 2x1 or 1x1 and report back the number of ways to do it.

This is a pretty standard DP problem. The idea is that we systematically fill from the left and track how many ways the "front' of trays can look. It turns out there are 8:

#
#
#

X
#
#

#
X
#

#
#
X

X
X
#

X
#
X

#
X
X

X
X
X

So DP[i][j] stores the number of possible ways to place trays such that the "front" in column i looks like the j-th of the 8 above configurations.

The next step is to figure out for each of the above configurations which trays can be placed to fill out that row.

• an empty row has 12 ways (i'll let you find them all!)
• a row with the top or bottom box filled has 5 ways
• a row with the middle box filled has 4 ways
• a row with one box left unfilled has 2 ways
• a row with no boxes left unfilled has 0 ways

So for each [i][j] in the DP, we iterate over all possible configurations, and add the value of dp[i][j] to dp[i+1][new_j] for each new configuration we make (note, we may make the same configuration in multiple ways, so our value may get added to the same element twice!). (again, new_j is what the front of the NEXT column would look like if we filled our CURRENT row with the given configuration)

The array is something like 24 * 8, with a max of 12 new configurations for each, which is plenty fast.

The blocked cells are easy to deal with. We just have to ensure we don't choose one of the configurations which would cover it.

Implementation note

I think the easiest way to deal with iterating over the configurations is to simply pre-compute which of the 8 configurations it makes in the next column.

So for the empty row:

• if we put 3 1x1 tiles, our new_j is "0," since we're in the 0th configuration (no blocks reached the next row)
• if we put a 2x1 vertically and then a 1x1, our new_j is still 0
• if we put a 2x1 horizontally and then a 2x1 vertically, our new_j is 1, since only the top row stuck out into the next row

You can perform this for all 12 scenarios and just put them in a list {0,0,1,...} and then just walk the list and add the current value to dp[i+1][list[x]]