### Broken profile dynamic programming

Consider the following problem.

Problem: In how many ways can you fill an $n \times m$ board with $2 \times 1$ dominoes such that whole board is covered and no two dominoes overlap with each other?

Constraints:
$1 \leq n \leq 9$
$1 \leq m \leq 1000$

Solution: One way of solving this problem is to obtain a recurrence relation for a given $n$ in terms of $m$. For example, if $n = 2$, we  get the recurrence relation
$f_{m} = f_{m-1} + f_{m-2}$ And if $n = 3$, we get the recurrence relation
$f_{m} = 4f_{m-1} - f_{m-2}$Click here for detailed explanation on above recurrence relations.

But obtaining recurrence relation becomes harder as $n$ increases. So, instead we shall approach this problem in a different way. Let us define profile of some column as an n-bit binary integer which gives information of the occupancy of blocks in that column i.e. if $i$th bit is equal to $1$ then $i$th block in that column is occupied by some domino and if it is equal to $0$ then it is not occupied. Let us define our DP state as $dp[i][p]$ (1-based indexing) which is equal to numbers of ways of filling first $i$ columns completely with dominoes (without leaving any block as empty). Here $p$ is the profile of $(i+1)$th column obtained after filling first $i$ columns. Note that, the $(i+1)$th column should not contain a complete domino as our intention is to use dominoes for filling the first $i$ columns. Here is an example.

But how do we obtain the relation between the states? One way is to obtain the value of $dp[i][p]$ from $dp[i-1][q]$ by expressing the former as the sum of all $dp[i-1][q]$ for which there exists a filling of $(i)$th column with dominoes, leaving the $i+1$th column with profile $p$. Time complexity for calculating $dp[i][p]$ is equal to $O(2^n)$. As there are $m \times 2^n$ states, so the total time complexity becomes equal to $O(m \times 2^{2n})$.

But we would get TLE verdict for above algorithm. To avoid this, instead of finding all possible profiles $q$ such that $dp[i-1][q]$ can produce $dp[i][p]$, for a given profile $q$ we find all possible profiles $p$ such that $dp[i-1][q]$ can produce $dp[i][p]$ and add the value of $dp[i-1][q]$ to $dp[i][p]$. This means that we check all possible ways of filling the $i$th column which has profile $q$. To do this let us analyse the $i$th column from $1$st block of the column to $n$th block of the column.

If the $j$th block is already occupied by some domino, then do nothing.
Else, this block can be filled in at most two ways as listed below
1. Place a domino in blocks $(i,j)$ and $(i+1,j)$ and mark them as occupied.
2. Place a domino in blocks $(i,j)$ and $(i,j+1)$ and mark them as occupied if ($j+1)$ block exists and is unoccupied.
Each permutation filling the current column produces a unique profile $p$ representing the $(i+1)$th column. So we add $dp[i][q]$ to $dp[i+1][p]$ where $q$ is the profile of $i$th column before filling.

Now, observe that for $i = 0$, filling first $0$ columns completely and having profile $p$ for $1$st column is possible iff $p = 0$. This implies that $dp[0][p]$ is equal to $1$ for $p = 0$ and equal to $0$ for all $p \neq 0$.

Since we need to fill all $m$ columns with the profile for $(m+1)$th column equal to 0 (as there exists no $(m+1)$th column), the required answer is equal to $dp[m][0]$.

Run Time Analysis: For a particular column with $k$ empty blocks, the worst case run time of the above analysis is $O(f_{k})$, where $f_{k}$ is $k$th fibonacci number. There $^{n}C_{k}$ profiles with $k$ empty blocks. Also there are $m$  columns. So, the total run time is $m \times \sum_{k = 0}^{n}$ $^{n}C_{k} \times O(f_{k})$ which is equal to $O(m \times (1+ \phi)^n)$. Observe that this algorithm is very efficient than the previous one.

Source for this topic.

P.S. This is my first blog post. Any constructive feedback is welcome :).

Practice Problems:
1. Same problem but with $3 \times 1$ dominoes.
2. Mosaic

Code: