动态编程平铺

Question

http://www.spoj.pl/problems/GNY07H/ 在这个问题中,我们必须找到在4Xw(w> = 1)矩形中排列2X1瓦片的多种方法？我已经尝试过这个问题并给了它很多时间,但却无法提出任何解决方案.如何处理这类问题.意思是如何让dp重复出现.？

Answer 1

您可以逐行构建4xW矩形.构建下一行时,上一行可以处于6种不同的状态:

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

例如,如果前一行是(5),则必须放置两个垂直多米诺骨牌,然后下一行将是(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)(最后一行填写).

Answer 2

从上面的链接:"这是最强大的DP状态域类型.它通常用于平铺或覆盖特殊图形上的问题.经典的例子是:计算用多米诺骨牌平铺矩形板的方法的数量(某些单元格不能是尽可能多地把棋子放在棋盘上,这样他们就不会相互碰撞(同样,一些细胞也可能受到限制)."

有关此技术的其他更平易近人的教程可在以下位置获得:

我也在努力解决这些问题.

这不是您提出的特定问题的答案,而是解决此类问题时人们遵循的一般技术.