algorithm - 4xN多米诺骨牌砖的组合数

我想通过动态编程找到一个4x N区域（4个单位宽度和N个单位高度，N≥1）的domino块的可能不同组合的数量。
多米诺砖块的尺寸为2x1，例如

==

对于水平和

|
|

竖直的砖块。
现在，
示例4x1（两块多米诺砖块相互下面）

====

4x2砖块配置示例（共5个）
（一）

||||
||||

2）（右转两块砖）

||==
||==

三）

|==|
|==|

（四）

====
====

五）

==||
==||

目前已知的唯一组合数

4x1 : 1 possibility
4x2 : 5 possibilites
4x3 : 11 possibilites
4x4 : 36 possibilites

最佳答案

解决一个更普遍的问题找出平铺4×n网格的方法数，其中最上面一行中的某些位置可能被占用。将每个位置与2的幂相关，最左边对应1，第二个对应2，第三个对应4，最右边对应8设T(N,k)为4×n网格的平铺数，其中顶行中k对应的位置已被占用。k == 0表示没有位置被占用，k == 6表示两个中间位置被占用（6=2+4）等。
然后找到转换，当填充顶行的剩余部分时，下一行中的哪些模式可以通过多少种方式访问？
例如，如果中间两个位置被占用，填充顶行其余部分的唯一方法是在最左边和最右边的位置垂直放置一个domino，从而

|xx|
|  |

以及下一行中两个最外面的位置被占用的配置，对应于1+8 = 9，所以T(N,6) = T(N-1,9)。对于k == 9，我们从

|  |

我们有两种可能，

|==|     ||||
          ||

我们可以通过水平放置一个多米诺骨牌来填补空白，让下一行完全自由，或者垂直放置两个多米诺骨牌，占据下一行的两个中间位置，所以

T(N,9) = T(N-1,0) + T(N-1,6)

使用这些转换构建T(n,k)的表。
要查找的值是T(N,0)。

关于algorithm - 4xN多米诺骨牌砖的组合数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10727920/