The well-known Parquet Problem asks the following: Given an N x M board, find the number of ways to tile it using only 1 x 2 or 2 x 1 tiles. We can solve this with various DP formulations that result in various time complexities, but one thing all these methods have in common is the use of the "DP on Broken Profile" method — that is, using a bitmask to represent the state of a certain set of cells (usually a row or column).

My question is: Can someone fully explain the DP state for the $$$O(2^NNM)$$$ DP-on-Broken-Profile approach to this problem, including how the base cases fit conceptually with the overall process? (As for the transitions, I'm (possibly wrongly) assuming that once I fully understand the DP-state, the transitions will be trivial)

The only explanation I could find for this approach comes from USACO Guide. However, the explanation is confusing and seems to include

My understanding of their DP-state is that $$$dp[i][j][mask]$$$ = the number of ways to tile the grid so that basically columns 0 to $$$j - 2$$$ are all completely filled. Meanwhile, column $$$j - 1$$$ may not be completely filled, but must be filled from rows 0 to $$$i$$$. And $$$mask$$$ represents whether or not rows 0 to $$$i$$$ in column $$$j$$$, and rows $$$i + 1$$$ to $$$N - 1$$$ in column $$$j - 1$$$, are filled. Below is their explanation:

This explanation fits with the picture. But, when I actually run their provided program, I get DP-values that don't seem to agree with my understanding. Mainly, I don't understand what the DP-state means conceptually when $$$j = 0$$$. For instance, one value we get is that $$$dp[1][0][0011] = 1$$$. Based on my understanding, this basically 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??