Evilbuggy

Prerequisites:  Dynamic Programming, Bit masking 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 gi...