algorithm - レゴ ブロック - 動的プログラミング

Question

次のDPの問題を解決しようとしています:

サイズが 1 * 1 * 1、1 * 1 * 2、1 * 1 * 3、および 1 * 1 * 4 の 4 種類のレゴ ブロックがあります。各タイプのブロックが無数にあるとします。

これらのブロックで高さ H、幅 M の壁を作りたいとします。壁に穴があいてはいけません。構築する壁は、1 つの堅固な構造である必要があります。頑丈な構造とは、壁の構築に使用されるレゴ ブロックを切断せずに、垂直線に沿って壁を分離することができないことを意味します。ブロックは水平にのみ配置できます。壁を作る方法は何通りありますか?

これが私が試みている方法です: abcd で 1 * 1 * 1、1 * 1 * 2、1 * 1 * 3 および 1 * 1 * 4 ブロックを表します。有効なパターンは太字で示されています。無効なパターンは、縦線によって分割される可能性があるパターンです。

H=1 & W=3 #有効なパターン=1
aa ab ba c

h = 2＆w = 3 #valid pattern = 9

これを高さまたは幅で拡張する繰り返しパターンを見つけようとしています。つまり、H=3 & W=3 または H=2&W=4 の値を見つけようとしています。

身長または体重でこの成長を公式化する方法についての入力はありますか?
PS 壁は常に H*W*1 です。

Answer 1

まず、接続を維持する必要性を無視した場合に、いくつの M*N 壁を構築できるかを見てみましょう。

各行を個別に処理し、独立しているためカウントを乗算できます。

0*1aまたは1*1壁をタイル張りする方法は 1 つしかなく、タイルする方法の数はタイルする方法n*1の数の合計{n-1}*1です ...{n-4}*1サイズの壁、これらの壁は最後のタイルを取り除くことによって取得できるためですn*1壁の。

これにより、テトラナッチ シーケンスOEIS A000078が発生します。すべてのW*H壁の数は ですa(w,h)=T(w)^h。

次に、壁の数を数えます。MBo の回答には、基本的な前提が既に含まれています。

壁がつながっていない一番左の場所で分岐。All W*H 壁の数は、olid SX*H 壁の数にAll{W-X}*H壁の数を掛けたものであり、 のすべての可能な値を合計し、さらにolid W*H 壁Xの数を加えたものです。S

A(W,H) = sum{X=1..{W-1}}(S(X,H)*A(W-X,H)) + S(W,H)

最後のステップとして、S(M,H)計算したい値である項を分離し、前の式を繰り返します。

S(W,H) = A(W,H) - sum_x( S(X,H)*A(W-X,H) ) //implicitly, S(1,H)=1

A(W,H) = T(W)^H

T(X)   = X > 0: T(X-1)+T(X-2)+T(X-3)+T(X-4)
         X = 0: 1
         X < 0: 0

(MBo の式が正しいことを証明します)。

これは、O(W^2)計算するアルゴリズムも提供しますS(適切なメモ化と一定時間の算術演算を前提としています) 。

Answer 2

1xW ストライプの数を見つけるのは難しくありません (N(1,W) とします)。次に、すべての (非ソリッドを含む) HxW 壁の数を見つけることができます - それは A(H,W) = N(1,W)^H です 非ソリッド壁は左 H*L 壁と右 H* で構成されます(WL) 壁。固い壁の数は

S(H,W) = A(H,W) - Sum(S(H, L) * A(H, W-L)) [L=1..W-1]

S(H, L) * A(H, WL) は、L 垂直位置で左端のブレークを持つ非ソリッド ウォールの数です。最初の要因は、繰り返しバリアントのカウントを排除するためのソリッド ウォールの数です。