レゴブロック - 動的計画

Question

私は、次のDPの問題解決しようとしている

：あなたは、サイズの1 * 1 * 1、1 * 1 * 2、1 * 1 をレゴブロックの4種類があり

を* 3と1 * 1 * 4.各タイプのブロックが無限にあるとします。

これらのブロックの高さHと幅Mの壁を作りたいとします。 壁に穴があってはなりません。あなたが構築する壁は の1つの立体構造でなければなりません。頑丈な構造とは、壁を構築するために使用されたレゴブロックを切断することなく、任意の垂直線に沿って壁を切り離すことが可能であることを意味するものではありません。 ブロックは水平方向にのみ に配置できます。壁は何通り建てられますか？ここで

私はそれをしようとしています方法です：BはD = で* 1 * 1 1、* 1 * 2、* 1 1 * 3と1 * 1 * 4ブロックを表す 。有効なパターンは太字で示しています。無効なパターンは、縦線で壊れる可能性があります。

H = 1 & W = 3 #validパターン= 1
AA、AB、BA C

H = 2 & W = 3 #validパターン= 9

私はH = 3の値を見つけるためにheightまたはwidth.ieでこれを拡張するために繰り返しパターンを見つけようとしています& W = 3またはH = 2 & W = 4。

身長と体重による成長のフォーミュラ化の方法についての情報はありますか？
P.壁は常にH * W * 1です。

Answer 1

1xW個のストライプを見つけるのは難しくありません（N（1、W）とします）。 次に、H（H、W）= N（1、W）^ H のすべての非固体壁を見つけることができます。 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、W-L）がL垂直位置における左端ブレーク非固体壁の数があると思われます。第1因子は、反復型の数をなくすための、頑丈な壁の数です。

Answer 2

まず、我々が接続されてそれらを維持する必要性を無視した場合M * Nの壁は、我々が構築することができますどのように多くのを見てみましょう：

我々は個別にそれぞれの行を処理した後、彼らは独立しているので、カウントを掛けることができます。

0*1または1*1壁、タイルn*1に、いくつかの方法がタイル{n-1}*1に、いくつかの方法の総... {n-4}*1 -sized壁、これらであることの理由であるタイルへの唯一の方法がありますn*1壁の最後のタイルを取り除くことによって壁を得ることができます。

これは、テトララッチ配列OEIS A000078を生じる。 W*Hの壁の総数はa(w,h)=T(w)^hです。

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

壁が接続されていない最も左の場所に分岐します。

： A LLのW * Hを壁の数は SオリッX * H壁の数倍 Xのすべての可能な値にわたって合計 A LL {W-X}*H壁、数、プラス SオリッW * Hの壁の数であります

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の式は正しい証明を）。

これはまたS