algorithm - 特定の次元の直方体を作成できる方法の数

Question

私はインタビューでこの問題を尋ねられました。すべての可能性、つまり完全な総当たり攻撃以外の方法を見つけることができませんでした。

1×1×1、1×2×1、1×1×2の3種類の立方体があります。上記のタイプの立方体を使用して、寸法1×2 ⁿ ×kの立方体を作成する方法はいくつありますか？

Answer 1

この質問を減らすために、私は1つの定数次元を削除します。

この質問は簡単です：

1 * 1,1*2の正方形が2種類あります。

上記のタイプの正方形を使用して、寸法2 ^ n X kの正方形を作成する方法はいくつありますか？

そして、この質問は次のように等しくなります。2^ n X kサイズの格子グラフで一致するものはいくつありますか？

なぜなら、一致するたびに、正方形を埋めるための1つのパターンがあり、そのセット（1 * 2の正方形）はエッジが一致します。他の正方形のセット（1 * 1の正方形）の場合

マッチング多項式と2部グラフが役立つと思います。

同じ質問で（n = 1）を使用すると、再帰関数を使用してそれを解決できます。結果がfibonacci_numberとCatalan_numberの間にあることを簡単に証明できます（詳細については、このリンクのフィボナッチ数とレンガの壁のパターンを参照してください） 。