我很想知道解决这个问题的算法。问题陈述的正式描述是这样的-给定N(
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)=“如果第i列包含0,0，则从第i列填充的组合数”，f01(i)=“要填充的组合数从第i列开始，如果第i列包含0,1”，f10(i)=“如果第i列包含1,0，则从第i列填充的组合数”，f11(i)=“从第i列开始，填充的组合数第一栏包含1,1“
显然f00(n)= f11(n)= 1，f01(n)= f10(n)= 0。
f00(i)如果i
i
f01(i)的工作原理相同。
f11(i)= f00，f01，f10或f11(i + 1)，具体取决于下一列中的内容。
解决方案很容易在线性时间内找到。