I find it easier to think in terms of a n × m grid. You are supposed to place a 1 × 2 tile or 1 × 1 tile or cover two cells of the same colour in adjacent rows, and we have to find the number of ways to tile the grid. You just run across the grid in row-wise order choosing how the next cell is tiled. If we choose the special tiling(same colour in adjacent rows), then we have to remember to not tile the next occurrence of this colour(that is, the occurence in the next row). So, it is natural to keep a set(a bitmask) of the colours that we have to ignore as we run across. So, the dp state is (x, y, colours that you ignore). Now, if the next cell is one of the colours that I ignore, update the set and continue forward. Otherwise, we choose how to tile the current cell. If it is going to be tiled by a 1 × 1 tile, you continue forward. If it is a special tile, you update the set asking to ignore the next occurrence of this colour. Finally, if it is a 1 × 2 tile, you have to make sure that the next 2 cells(the current one and the next one) are in the same row and that you cannot ignore the next 2 cells. If so, tile that way. Check out Endagorion's clear implementation for the same.