1

動的計画法を使用して、ドミノレンガの4 x N領域（幅4単位、高さN単位、N≥1）の可能なさまざまな組み合わせの数を見つけたいと思います。

ドミノブリックのサイズは2x1です。

==

水平および

|
|

垂直レンガの場合。

今、

例4x1（互いに下にある2つのドミノレンガ）

====

4x2ブリック構成の例（合計5つ）

1）

||||
||||

2）（右側の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番目、3番目、4番目、右端は8に対応します。一番上の行に対応する位置がすでに占有されてT(N,k)いる4×Nグリッドのタイリングの数とします。ポジションが占有されていないことを意味し、2つの中央のポジションが占有されていることを意味します（6 = 2 + 4）など。kk == 0k == 6

次に、一番上の行の残りを埋めるときに、次の行のどのパターンにいくつの方法で到達できるかという遷移を見つけますか？

たとえば、真ん中の2つの位置が占有されている場合、一番上の行の残りを埋める唯一の方法は、ドミノを左端と右端の位置に垂直に配置することです。

|xx|
|  |

そして、次の行の最も外側の2つの位置が占有されている構成。これは、に対応し1+8 = 9ますT(N,6) = T(N-1,9)。そして、k == 9のために、私たちがルックスから始める状況

|  |

2つの可能性があります。

|==|     ||||
          ||

1つのドミノを水平に配置して次の行を完全に解放するか、2つのドミノを垂直に配置して次の行の中央の2つの位置を占めることで、ギャップを埋めることができます。

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 に答える