我无法将递归关系写成如下问题。
给定一个尺寸为 4 xn 的矩形网格，有多少种方法可以用 2 x 2 和 2 x 1 多米诺骨牌完全平铺网格？
在这里，对于 2 x 1 矩形，它做得很好，但我不知道矩形是否是 2 x 1 和 2 x 2： http ://www.acmgnyr.org/year2007/hc
有任何想法吗？
例如对于
4x1：1 路
4x2：11 种方式
4x3：29 种方式
下面的代码使用蛮力生成所有可能性。但我想使用动态编程来做到这一点。
问问题
2761 次
2 回答
2
我认为您可以通过使用动态编程算法来解决这个问题。
想象一下，不是将网格表示为 4 xn 的正方形网格，而是表示为表示每个单独列的宽度的 4 元组。每次放置瓷砖时，您都可以尝试将其放置在某个位置，使其其中一个方块接触到网格最左侧的左上角。这样做的效果是改变每列的有效宽度。例如，给定这个 4 x 3 网格：
. . .
. . .
. . .
. . .
我们将其编码为 (3, 3, 3, 3)。如果你要在上角放置一个 2 x 2 块，你会得到：
X X .
X X .
. . .
. . .
这将被编码为 (1, 1, 3, 3)，因为前两行现在实际上要小得多。
这表明了一种初始（低效）递归算法。作为您的基本情况，世界 (0, 0, 0, 0) 只有一个解决方案（即，什么都不做）。任何没有合法方式放置覆盖最左侧行最上面方块的瓷砖的世界都没有解决方案。否则，对于所有可能的移动，进行移动，更新世界的内部表示，并递归地添加您可以在那个较小的世界中找到的所有解决方案。
这是非常缓慢的（指数级的），但可以显着加快。特别要注意，可能的 4 元组的数量是 (n + 1) 4。这意味着唯一递归调用的最大数量是 O(n 4 )。因此，如果您记住递归调用或使用动态编程来向后计算调用，则只需进行多项式调用。记忆化应该很容易添加到现有的递归解决方案中，并且加速应该非常巨大。
如果您正在寻找一种在数学上更精确的方法来解决这个问题，请考虑尝试为这个问题编写一个生成函数并使用它来导出一个封闭形式的解决方案。一旦你有了它，直接评估它应该不会比上述解决方案更有效。但是，由于我不是生成函数的专家，因此我实际上不确定您将如何做到这一点。
希望这可以帮助！
于 2013-01-12T18:05:14.243 回答
0
在4xn中，n要么是偶数，要么是奇数。如果n是偶数，只需使用2x2多米诺骨牌。否则，2x2最多使用n-1. 然后使用两个2x1多米诺骨牌完成4x1剩余的块。在回答时，我没有关注您的链接，因为我认为问题已经充分说明，并且该链接只是您对更简单问题的回答。
n = 偶数
use n 2x2 dominoes
n = 奇数
use n-1 2x2 dominoes plus 2 2x1 domino
如果 n = 10 则 4*10=40 和 (2x2)*10=40
如果 n = 11 则 4*11=44 和 (2x2)*10=40 和 (2x1)*2=4 总共 44
于 2013-01-12T17:33:37.237 回答