1/13
Loading...
🧱廊下のタイル敷き!
幅2マス・長さ6マスの廊下を1×2 / 2×1タイルで隙間なく埋める場合の数を求めましょう。
Loading...
幅2マス・長さ6マスの廊下を1×2 / 2×1タイルで隙間なく埋める場合の数を求めましょう。
新人インテリア技師のドラは、幅2マスの長い廊下にタイルを敷かなければなりません。倉庫には1×2サイズ（横に寝かせた形）と2×1サイズ（縦に立てた形）の同じタイルだけが山積みになっています。廊下の長さがnマスのとき、隙間も重なりもなく廊下を埋め尽くす異なるタイルの並べ方は全部で何通りでしょうか？
3
3
長さ3の廊下を埋める方法は3通りです。縦タイル3枚 / 縦1枚 + 横2枚（前側）/ 横2枚（後側）+ 縦1枚。
6
13
長さ6の廊下は13通りで埋められます。dp[6] = dp[5] + dp[4] = 8 + 5 = 13。