以下のような質問に対して漸化式を書くことができませんでした。
寸法が4xnの長方形のグリッドがある場合、2x2および2x1のドミノでグリッドを完全に並べて表示する方法はいくつありますか？
ここでは、2 x 1の長方形の場合、それは大いに行われますが、長方形が2x1と2x2であるかどうかはわかりませんでした：http： //www.acmgnyr.org/year2007/hc
何か案は？
たとえば
4x1：片道
4x2：11の方法
4x3：29通り
以下のコードは、ブルートフォースを使用してすべての可能性を生成します。しかし、私は動的計画法を使用してそれをやりたいと思っています。
動的計画法アルゴリズムを使用することでこれを解決できると思います。
グリッドを4xnの正方形のグリッドとしてではなく、個々の列の幅を表す4タプルとして表すことを想像してみてください。タイルを配置するたびに、その正方形の1つがグリッドの左端の左上隅に接触するような場所にタイルを配置してみることができます。これを行うと、各列の有効幅が変更されます。たとえば、この4x3グリッドがあるとします。
. . .
. . .
. . .
. . .
（3、3、3、3）としてエンコードします。上隅に2x2のブロックを配置すると、次のようになります。
X X .
X X .
. . .
. . .
これは（1、1、3、3）としてエンコードされます。これは、上の2つの行が事実上はるかに小さいためです。
これは、初期の（非効率的な）再帰的アルゴリズムを示唆しています。基本的なケースとして、世界（0、0、0、0）には1つの解決策しかありません（つまり、何もしません）。左端の列の一番上の正方形を覆うタイルを配置する合法的な方法がない世界には、解決策がありません。それ以外の場合は、考えられるすべての動きについて、その動きを行い、世界の内部表現を更新し、その小さな世界で見つけることができるすべてのソリューションを再帰的に追加します。
これは非常に遅いですが（指数関数的にそうです）、劇的にスピードアップすることができます。特に、可能な4タプルの数は（n + 1）4であることに注意してください。これは、一意の再帰呼び出しの最大数がO（n 4）であることを意味します。したがって、再帰呼び出しをメモ化するか、動的計画法を使用して呼び出しを逆方向に計算する場合は、多項式の数の呼び出しを行うだけで済みます。メモ化は、既存の再帰的ソリューションに非常に簡単に追加できる必要があり、スピードアップは非常に大きなものになるはずです。
この問題を解決するためのより数学的に正確な方法を探している場合は、この問題の母関数を書き、それを使用して閉じた形の解を導出することを検討してください。それができたら、上記のソリューションよりもはるかに効率的に直接評価するのはそれほど難しいことではありません。ただし、私は関数の生成の専門家ではないため、実際にこれをどのように行うかはわかりません。
お役に立てれば！
で4xn、nは偶数または奇数のいずれかです。n偶数の場合は、2x2ドミノを使用してください。それ以外の場合は、2x2最大を使用しn-1ます。次に、2つの2x1ドミノを使用して4x1残りのブロックを終了します。質問は十分に述べられており、リンクはより単純な問題に対するあなたの答えであると私は思うので、答える際に私はあなたのリンクをたどりませんでした。
n=偶数
use n 2x2 dominoes
n=奇数
use n-1 2x2 dominoes plus 2 2x1 domino
n = 10の場合、4 * 10 = 40および（2x2）* 10 = 40
n = 11の場合、4 * 11 = 44および（2x2）* 10 = 40および（2x1）* 2 = 4、合計44