Geek asks and answers

Dynamic programming tiles

http://www.spoj.pl/problems/GNY07H/ In this question we need to find several ways to arrange 2X1 tiles in a 4Xw rectangle (w> = 1)? I tried this question and devoted a lot of time to it, but could not find a solution. how to approach these types of problems. which means how to do dp repeat for them.

+3
source share
4 answers

You can build a 4xW rectangle in turn. When you build the next line, the previous line 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 line is (5), you must put two vertical dominoes, and then the next line will be (3):

XXXX
XABX
-AB-

X(W,q) 4xW, q, .

X(W-1,q) 6 q, X(W,q).

X(1,q) (q = 1..6 → 1, 1, 1, 1, 1, ). , W W.

: X(W,1) ( ).

+9

: , , ( ) - ( , , , ).

, , .

0

Just select a template if, having deleted any 2 * 1 block, a template (hemotrossia) arises so that it again is an intermediate result, then it gives a recursive function. From this, just create a DP from it.

For your problem just view the link. This will explain everything.

https://math.stackexchange.com/questions/664113/count-the-ways-to-fill-a-4-times-n-board-with-dominoes

For more information, see the IOI Training Link

http://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php

0
source

More articles:


All Articles