用 2 x 1 和 1 x 2 多米诺骨牌平铺宽 x 高网格的方法有多少种？

Question

编写一个程序，将网格的宽度、W 和高度 H 作为输入，并输出用 (2x1) 多米诺骨牌平铺 W×H 网格的不同方式的数量

\n\n

我知道如何用 3 x N 网格解决问题，但是为此编写递归公式对我来说太难了！

\n\n

我不知道该怎么做！

\n\n

我创建了两个函数 F(n) - 平铺直到 N 的完整方法和 S(n) 用于 3 x N 的不完全平铺方法的数量！但这里由于高度是可变的我想不出任何东西

\n\n

\n\n

约束：(0 \xe2\x89\xa4 W+H \xe2\x89\xa4 22)

\n

Answer 1

这有点像 DPish 的幕后黑手。这个想法是 IVlad 的：通过记忆进行回溯。

memo = {}


def count_tilings_recursive(uncovered):
    if len(uncovered) & 1:
        return 0
    if not uncovered:
        return 1
    if uncovered not in memo:
        i, j = min(uncovered)
        memo[uncovered] = count_tilings_recursive(uncovered - {(i, j), (i, j + 1)}) + count_tilings_recursive(uncovered - {(i, j), (i + 1, j)})
    return memo[uncovered]


def count_tilings(m, n):
    return count_tilings_recursive(frozenset((i, j) for i in range(max(m, n)) for j in range(min(m, n))))


print(count_tilings(18, 4))

这里的技巧是防止状态数量激增。首先，我们总是选择最左边然后最上面的方块来覆盖，这样部分覆盖可以描述为按从最左边到最上面的顺序连续被覆盖的方块的数量，然后是部分覆盖的#rows，总共最多(#rows) * #columns + 1) * 2^#rows 状态。其次，我们调整网格的方向，使列数至少与行数一样多，并以 10 为界，以进行有趣的计算（因为 11 x 11 是微不足道的）。