c++ - 用 2x1 和 1x2 多米诺骨牌拼贴 2xN 网格的方法有多少种？

Question

我很想知道解决这个问题的算法。问题陈述的正式描述是这样的——给定 N(<100) 和多米诺骨牌 2x1 和 1x2 我必须找到可能的不同网格平铺的数量。这里的区别是有些单元格会被涂黑以表示禁止位置。

Input:
5
01000
00010

Output:
1

输入中的 0 代表一个空单元格和 1 个禁止单元格。 我在这里发现了一个类似的问题 Hexagonal Grid Tiling .尽管略微提到了使用带位掩码的动态编程来解决这类问题，但我无法找到有关此技术的任何详尽解释。

PS:虽然我知道如何解决一般的网格平铺问题，但在这个问题中，只有当我们只给出空单元格时，递归才能形成为 F(n) = F(n-1) + F (n-2)，通过放置一个 1x2 多米诺骨牌或放置两个 2x1 多米诺骨牌分别覆盖第一列和前两列。这可以迭代解决，甚至对于大 N(比如 > 10^7)我们可以使用矩阵求幂技术。但我有兴趣了解通过 DP+Bitmasks 解决此类问题的技术。任何帮助将不胜感激。

Answer 1

对于 i = n, n-1, ..., 1 您计算 f00 (i) = "如果第 i 列包含 0,0，则从第 i 列填充的组合数"，f01 (i) = "Number of如果第 i 列包含 0,1"，则从第 i 列填充的组合"，f10 (i) = "如果第 i 列包含 1,0，则从第 i 列填充的组合数"，f11 (i) = "从第 i 列填充的组合数第 i 列如果第 i 列包含 1,1"

显然f00(n)=f11(n)=1,f01(n)=f10(n)=0。

f00 (i) if i < n:无论下一列是什么，您都可以使用一个垂直图 block ，如果下一列是 (0, 0)，则可以使用两个水平图 block 。所以如果下一列是 (0, 0) 那么结果就是 f00 (i + 1) + f11 (i + 1);如果下一列是 (0, 1)、(1, 0) 或 (1, 1)，则 f00 (i) = f01、f10 或 f11 (i + 1)。

f10 (i) for i < n: 你必须使用一个水平方 block 。如果下一列包含 (0, 1) 或 (1, 1)，则结果为 0；如果下一列包含 (0, 0) 或 (1, 0)，则结果为 f01 (i+1) 或 f11 (i+1)。

f01 (i) 的工作原理相同。

f11 (i) = f00、f01、f10 或 f11 (i + 1)，具体取决于下一列中的内容。

解决方案很容易在线性时间内找到。