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

本文介绍了4xN多米诺骨牌砖的组合数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I want to find the number of possible different combinations for a 4 x N area (4 units width and N units height, N ≥ 1) of domino bricks using dynamic programming .

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

Domino bricks have a size of 2x1 e.g.

==

水平的

| |

垂直砖。

现在，

示例4x1（两个下方的多米诺骨牌）

Example 4x1 (two domino bricks beneath each other)

====

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

Examples for 4x2 brick configurations (5 in total)

1）

|||| ||||

2）（在右侧转动两块积木）

2) (Turn two bricks on the right)

||== ||==

3）

|==| |==|

4）

==== ====

5）

==|| ==||

到目前为止已知的唯一组合数

Number of unique combinations known so far

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

推荐答案

解决一个更普遍的问题。找到在顶部行中的某些位置可能会被占用的4×N网格的平铺方法。将每个位置的2的幂次幂关联到最左边，对应于1，第二个2，第3个，最右边的8。令 T（N，k）为a的平铺数。 4×N网格，其中与上一行 k 相对应的位置已被占用。 k == 0 表示无头寸， k == 6 表示两个中间头寸均被占用（6 = 2 + 4）等。

Solve a more general problem. Find the number of ways to tile a 4×N grid where some of the positions in the top row may be occupied. Associate each position with a power of 2, leftmost corresponds to 1, second 2, third 4, rightmost 8. Let T(N,k) be the number of tilings of a 4×N grid where the positions corresponding to k in the top row are already occupied. k == 0 means no position occupied, k == 6 means the two middle positions are occupied (6 = 2 + 4) etc.

然后找到过渡，当填充第一行的其余部分时，下一行中的哪些模式可以通过几种方式访问​​？

Then find the transitions, when filling the remainder of the top row, which patterns in the next row are reachable in how many ways?

例如，如果居中的两个位置被占用，则填充顶行其余部分的唯一方法是将多米诺骨牌垂直放置在最左边和最右边的位置，从而导致

For example, if the middle two positions are occupied, the only way to fill the remainder of the top row is to place a domino vertically in the leftmost and the rightmost position, leading to

|xx| | |

以及下一行中两个最外侧位置被占用的配置，对应于 1 + 8 = 9 ，所以 T（N，6）= T（N-1,9）。对于 k == 9 ，我们从外表开始的情况

and a configuration in which the two outermost positions in the next row are occupied, that corresponds to 1+8 = 9, so T(N,6) = T(N-1,9). And for k == 9, the situation we start from looks

| |

我们有两种可能性，

|==| |||| ||

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

we can either fill the gap by placing one domino horizontally, leaving the next row completely free, or place two dominoes vertically, occupying the two middle positions of the next row, so

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

使用这些转换来建立表 T（n，k）。

Use these transitions to build a table of the T(n,k).

您要查找的值是 T （N，0）。