Skip to main content

## Posts

Showing posts from May, 2018

### Broken profile dynamic programming

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 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…