Glad that I am not the only one having a really hard time understanding DP on broken profile. This problem has been bugging me for more than an year now. Hope someone explains. Bump.

"dp[1][0][0011]=1. Based on my understanding, this represents the number of ways to tile only the leftmost-column, and only the bottommost two cells, so 1 does make sense here.

But dp[1][0][1100]=0! Shouldn't this just equal 1 as well, since it represents the number of ways to tile only the top two squares of the leftmost column??"

Why it doesn't make sense? dp[1][0][0011] = 1:

• You are at column 0, row 1.

• 0011

  1. bit 0 and bit 1 equal 0, which means a[0][0] and a[0][1] is not empty --> they are filled with a vertical 1x2 tile
  2. bit 2 and bit 3 equal 1, which means a[2][-1] and a[3][-1] is empty, that's true because the column -1 is outside of the board

• 1100 is basically flip the mask so one value must be 0 and the other must be 1.

so the problem is: the mask in the DP state of the USACO Guide means: whether or not the cells are empty but you misunderstood the mask as: whether or not the cells are filled

hope this helps

USACO denotes mask as the mask of columns, but I'd rather use it as a mask of rows because I think it's easier to imagine.

denote $$$dp[i][j][mask]$$$ as the number of ways to get the state of:

1. $$$((0, 0)$$$ to $$$(i-1, j))$$$ and $$$((i-2, j+1)$$$ to $$$(0, m-1))$$$ are filled.

2. $$$((i, 0)$$$ to $$$(i, j))$$$ + $$$((i-1, j+1)$$$ to $$$(i-1, m-1))$$$ is denoted by mask of size m.

3. and the rest of the cells are empty.

notes:

• if $$$j'th$$$ bit of mask is 0. it means it's empty, otherwise, it means it's filled.
• if $$$j'th$$$ bit of mask is 0, it means we left it empty for now, and we need to fill it with a vertical tile from below or with a horizontal tile from right later.

Now we get some transitions that solves the problem using the states above:

if $$$j'th$$$ bit of mask is 1 while we're at $$$(i, j)$$$ and want to consider the case where we put a vertical tile on $$$((i-1, j), (i, j))$$$:

• $$$dp[i][j][mask]+= dp[i][j-1][mask\bigoplus 2^{j}]$$$

if $$$j'th$$$ bit of mask is 1 while we're at $$$(i, j)$$$ and $$$j-1'th$$$ bit is also 1 and we want to consider the case where we will put horizontal tile on $$$((i, j-1), (i, j))$$$:

• $$$dp[i][j][mask]+= dp[i][j-1][mask\bigoplus 2^{j-1}]$$$ (we are keeping $$$j'th$$$ bit open because it denote cell $$$(i-1, j)$$$ which has to be already filled when we put horizontal tile at $$$(i, j)$$$. otherwise, we wouldn't ever be able to fill it back.)

if $$$j'th$$$ bit is 0 while we're at $$$(i, j)$$$ and we want to consider the case where we leave it empty:

• $$$dp[i][j][mask]+= dp[i][j-1][mask\bigoplus 2^{j}]$$$ (same case as previous one, we have to keep cell $$$(i-1, j)$$$ closed because otherwise, we wouldn't be able to close it later.)

base cases:

$$$j = 0:$$$

if $$$j'th$$$ bit of the mask is 0 and we consider leaving it empty:

• $$$dp[i][0][mask]+= dp[i-1][m-1][mask\bigoplus 2^{j}]$$$

if $$$j'th$$$ bit of the mask is 1 and we consider placing vertical a tile:

• $$$dp[i][0][mask]+= dp[i-1][m-1][mask\bigoplus 2^{j}]$$$

$$$i = 0:$$$

• just assume $$$dp[-1][m-1][111...1] = 1$$$