c - 动态编程磁贴

http://www.spoj.pl/problems/GNY07H/
在这个问题中，我们必须找到在4xw（w>=1）矩形中排列2x1瓷砖的方法？
我试过这个问题，花了很多时间，但没有想出任何解决办法。如何解决这些问题。意思是如何使dp重现。是吗？

最佳答案

您可以逐行构建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状态，其余行完全填充。
如果您知道所有6个状态的X(W-1,q)，您可以轻松计算q。
你知道初始状态（q=1..6->1，1，1，1，1，1，1，无效）。所以你可以增加w，得到每个w的数字。
最终结果是X(W,q)（最后一行已填充）。