algorithm - 带有 2 x 1 和 2 x 2 矩形的平铺网格

Question

我无法写出与下面这样的问题的递归关系。

给定一个尺寸为 4 x n 的矩形网格，有多少种方法可以用 2 x 2 和 2 x 1 的多米诺骨牌完全平铺网格？

这里对于 2 x 1 的矩形做得很好，但我不知道矩形是 2 x 1 还是 2 x 2:http://www.acmgnyr.org/year2007/h.c

有什么想法吗？

例如

4x1 : 1 路

4x2:11 种方式

4x3:29 种方式

下面的代码使用蛮力生成所有可能性。但我想使用动态规划来做到这一点。

https://gist.github.com/4519601

Answer 1

我认为你可以使用动态规划算法来解决这个问题。

想象一下，不是将网格表示为 4 x n 的正方形网格，而是表示为表示每个单独列的宽度的 4 元组。每次放置瓷砖时，您都可以尝试将其放置在某个位置，使其其中一个方 block 接触到网格最左侧的左上角。这样做的效果是改变每列的有效宽度。例如，给定这个 4 x 3 网格:

. . .
. . .
. . .
. . .

我们会将其编码为 (3, 3, 3, 3)。如果你要在上角放置一个 2 x 2 的方 block ，你会得到这个:

X X .
X X .
. . .
. . .

这将被编码为 (1, 1, 3, 3)，因为前两行现在实际上要小得多。

这表明初始的(低效的)递归算法。作为您的基本情况，世界 (0, 0, 0, 0) 只有一个解决方案(即什么都不做)。任何没有合法方法来放置覆盖最左边行的最上面正方形的图 block 的世界都没有解决方案。否则，对于所有可能的移动，执行该移动，更新世界的内部表示，并递归添加您可以在那个较小的世界中找到的所有解决方案。

这非常慢(呈指数级)，但可以显着加快。特别要注意的是，可能的 4 元组的数量是 (n + 1)⁴。这意味着唯一递归调用的最大次数是 O(n⁴)。因此，如果您记住递归调用或使用动态编程向后计算调用，则只需进行多项式调用。记忆化应该很容易添加到现有的递归解决方案中，并且加速应该是非常巨大的。

如果您正在寻找一种数学上更精确的方法来解决这个问题，请考虑尝试为这个问题写出一个生成函数并使用它来导出一个封闭形式的解决方案。一旦你有了它，直接评估它应该比上面的解决方案更有效地那么难。不过，由于我不是生成函数方面的专家，所以我实际上不确定您将如何执行此操作。

希望这对您有所帮助!