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

  • Z时代
  • 2024-01-10
  • 分类：问答

我想 使用动态编程 找到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×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)。

以上是 4xN多米诺骨牌砖的组合数 的全部内容， 来源链接： utcz.com/qa/399683.html

回到顶部