Target2018's blog

Tiling Problem
By Target2018, history, 7 years ago, In English

I was trying to solve this problem, but can't figure out the recurrence relation.Then I read this article but didn't understand this part, and I can't figure out the image of tiling, can anyone tell me about the recurrence of g(n) in the second part.And how can I solve this type of problems also?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't go through the article, but I will tell you how I solved it:

The width of the room is fixed at 2. The length is N.

For any one unit length, there can be 4 cases. Either the whole width is tiled, whole width is not tiled, width 0-1 is tiled, width 1-2 is tiled.

We can solve it by going 1 unit length ahead at a time. That is, we iterate from 0 to n-1, and calculate the number of ways such that all previous columns are completely tiled and current column is tiled in one of the 4 ways. We do it for all 4 ways.

So we have a 2D dp array dp[1000000][4].

Base case is dp[0][0] = dp[0][3] = 1, 0 meaning complete width tiled, 3 meaning completely untiled.

For all columns, use result of previous column and depending on shape of available tiles, calculate the answer.

Answer will be dp[n-1][0] (Number of ways n-1th column is completely tiled. Note that this means that all previous columns are also tiled.)

Code: https://pastebin.com/TXhbdP5k

→ Reply