Prerequisites: Dynamic Programming, Bit masking Consider the following problem. Problem: In how many ways can you fill an n×m board with 2×1 dominoes such that whole board is covered and no two dominoes overlap with each other? Constraints: 1≤n≤9 1≤m≤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 fm=fm−1+fm−2
And if n=3, we get the recurrence relation fm=4fm−1−fm−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...