1

我想使用动态编程找到多米诺砖的 4 x N 区域（4 个单位宽度和 N 个单位高度，N ≥ 1）的可能不同组合的数量。

多米诺砖的大小为 2x1，例如

==

对于水平和

|
|

对于垂直砖。

现在，

示例 4x1（彼此下方的两块多米诺骨牌）

====

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

1)

||||
||||

2）（转动右边的两块砖）

||==
||==

3)

|==|
|==|

4)

====
====

5)

==||
==||

迄今为止已知的唯一组合数

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

2 回答 2

2

解决一个更普遍的问题。找出平铺 4×N 网格的方法数，其中顶行中的某些位置可能已被占用。将每个位置与 2 的幂相关联，最左边对应 1，第二个 2，第三个 4，最右边 8。设T(N,k)4×N 网格的平铺数，其中顶行对应的位置k已经被占用。k == 0表示没有位置被占用，k == 6意味着两个中间位置被占用（6 = 2 + 4）等等。

然后找到转换，当填充顶行的其余部分时，下一行中的哪些模式可以通过多少种方式到达？

例如，如果中间的两个位置都被占用了，那么填充顶行剩余部分的唯一方法是在最左边和最右边的位置垂直放置一个多米诺骨牌，导致

|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).

于 2012-05-23T23:48:32.100 回答
1 
F[n] = number of ways to tile a 4-by-n grid
G[n] = number of ways to tile a 4-by-n grid with top-right and bottom-right
    squares uncovered
H[n] = number of ways to tile a 4-by-n grid with bottom-right 2
        squares uncovered
  = number of ways to tile a 4-by-n grid with top-right 2
        squares uncovered
if n >= 2, the right end of any tiling can be
    two vertical dominoes (F[n-1] ways)
    horz, horz vert (H[n-1] ways)
    horz, vert, horz (G[n-1] ways)
    vert, horz, horz (H[n-1] ways)
    4 horizontal dominoes (F[n-2] ways)
 F[n] = F[n-1] + G[n-1] + 2*H[n-1] + F[n-2];
 For G: the right end can be a vertical domino (F[n-1] ways)
        or two horizontal dominoes => top & bottom are horz = G[n-2]
        G[n] = F[n-1] + G[n-2];
 For H: the right end can be a vertical domino (F[n-1] ways)
        or two horizontal dominoes (H[n-1] ways)
        H[n] = F[n-1] + H[n-1];
 F[0] = 1, F[1] = 1, G[0] = 0, G[1] = 1, H[0] = 0, H[1] = 1

希望能帮助到你 ！！

于 2012-06-07T21:13:47.303 回答