Dynamic Programming Tiles

Question

http://www.spoj.pl/problems/GNY07H/ In this question we have to find number of ways to arrange 2X1 tiles in 4Xw (w >=1) rectangle ? I have tried this question and has given much time to it but was not able to come up with any solution . how to approach for these kinds of problem. meaning how to make dp recurrence for them. ?

Answer 1

You can build the 4xW rectangle row-by-row. When you build the next row the previous row can be in 6 different states:

XXXX (1 - filled)
XX-- (2)
-XX- (3)
--XX (4)
X--X (5)
---- (6 - empty)

For example if the previous row is (5), you have to put two vertical dominos, and then the next row is going to be (3):

XXXX
XABX
-AB-

Let X(W,q) denote the possible combinations of a 4xW rectangle where the last row is in state q and the rest is completely filled.

If you know X(W-1,q) for all the 6 q states you can easily calculate X(W,q).

You know the initial states X(1,q) (q=1..6 -> 1, 1, 1, 1, 1, invalid). So you can increase W and get these numbers for each W.

The final result is X(W,1) (last row filled).

Answer 2

I too am a beginner at this variation of Dynamic programming, but this link mentions http://apps.topcoder.com/forums/;jsessionid=A5053396424C9F9BBB9337ECAC9C6C17?module=Thread&threadID=770579&start=0&mc=2#1643035 that you need to apply "Dynamic programming with profiles", and that link also points to a tutorial http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0&mc=19 specifically, "layer count+ layer profile".

From the above link: "This is the toughest type of DP state domain. It is usually used in tiling or covering problems on special graphs. The classic examples are: calculate number of ways to tile the rectangular board with dominoes (certain cells cannot be used); or put as many chess figures on the chessboard as you can so that they do not hit each other (again, some cells may be restricted)."

Other more approachable tutorials on this technique are available at:

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_13.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_7469.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_6894.html

I'm working my way through them as well.

This isn't an answer to the particular question you asked, but more of a general technique that people follow when solving this class of problems.