用 2x1 和 1x2 多米诺骨牌拼贴 2xN 网格的方法有多少种？
Number of ways to tile a 2xN grid with forbidden positions with 2x1 and 1x2 dominoes?
我很想知道解决这个问题的算法。问题陈述的正式描述是这样的——给定 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 解决此类问题的技术。任何帮助将不胜感激。
对于 i = n, n-1, ..., 1 你计算 f00 (i) = "Number of combinations to fill from column i if column i contained 0,0", f01 (i) = "Number of combinations to fill from column i if column i contained 0,1", f10 (i) = "Number of combinations to fill from column i if column i contained 1,0", f11 (i) = "Number of combinations to fill from column i if column i contained 1,1"
显然f00(n)=f11(n)=1,f01(n)=f10(n)=0。
f00 (i) if i < n：无论下一列是什么，您都可以使用一个垂直图块，如果下一列是 (0, 0)，则可以使用两个水平图块。所以如果下一列是 (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: 您必须使用一个水平方块。如果下一列包含 (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)，具体取决于下一列中的内容。
在线性时间内很容易找到解决方案。
我很想知道解决这个问题的算法。问题陈述的正式描述是这样的——给定 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 解决此类问题的技术。任何帮助将不胜感激。
对于 i = n, n-1, ..., 1 你计算 f00 (i) = "Number of combinations to fill from column i if column i contained 0,0", f01 (i) = "Number of combinations to fill from column i if column i contained 0,1", f10 (i) = "Number of combinations to fill from column i if column i contained 1,0", f11 (i) = "Number of combinations to fill from column i if column i contained 1,1"
显然f00(n)=f11(n)=1,f01(n)=f10(n)=0。
f00 (i) if i < n：无论下一列是什么，您都可以使用一个垂直图块，如果下一列是 (0, 0)，则可以使用两个水平图块。所以如果下一列是 (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: 您必须使用一个水平方块。如果下一列包含 (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)，具体取决于下一列中的内容。
在线性时间内很容易找到解决方案。