2×nタイリングとは？
2×nタイリングは、幅2マス・長さnマスの長方形の廊下を、1×2（横に寝かせた）と2×1（縦に立てた）タイルで隙間も重なりもなく埋める場合の数を求める問題です。
動的計画法（DP）を初めて学ぶときに最も直感的な例の一つです。いくつか解を描いてみると、「端の列をどう覆うか」で場合がきれいに二つに分かれるのが目に見えます。
なぜ重要か？
- •漸化式設計の定石: 「最後の一片」を基準に場合分けする考え方が身につきます。
- •フィボナッチと同じ構造: dp[i]=dp[i-1]+dp[i-2]で、漸化式の入門に最適です。
- •コーディングテスト頻出型: タイリング・格子埋め系問題の基礎です。
漸化式を立てる
廊下の一番端の列をどう覆うか考えてみましょう。
ケース1. 端を縦タイル(2×1)1枚で覆う -> 前側に長さ i-1 の廊下が残る -> dp[i-1] 通り
ケース2. 端を横タイル(1×2)2枚を上下に重ねて覆う -> 前側に長さ i-2 の廊下が残る -> dp[i-2] 通り
二つのケースは重ならないので、足し合わせます。
dp[i] = dp[i-1] + dp[i-2]基底条件
- •dp[1] = 1（縦1枚）
- •dp[2] = 2（縦2枚 / 横2枚）
値を埋めてみる
| 長さ i | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dp[i] | 1 | 2 | 3 | 5 | 8 | 13 |
dp[3]=2+1=3, dp[4]=3+2=5, dp[5]=5+3=8, dp[6]=8+5=13。まさにフィボナッチ数列の形です。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n) |
| 空間（配列） | O(n) |
| 空間（変数2つ） | O(1) |
すべての部分問題を一度だけ計算するのでO(n)です。直前の2つの値だけ覚えれば、配列なしのO(1)空間でも解けます。
よくあるミス
- •基底条件の混同: dp[1]=1, dp[2]=2を正確に設定しましょう。dp[2]=1にすると全部ずれます。
- •タイル種類の誤解: 回転のみ許される1×2と2×1の2種類だけです。L字など他の形を混ぜると別問題になります。
- •重複計算: 再帰だけで解くとO(2^n)に爆発します。必ずメモ化かボトムアップDPを使います。
アルゴノートで直接確認しましょう
長さが増えるたびにdp[i]がdp[i-1]とdp[i-2]からどう作られるか、アルゴノートで一歩ずつ視覚的に確認できます。