HDU 1143 Tri Tiling：3×N 矩形鋪裝 2×1 多米諾骨牌的 DP 遞推

題目大意

用 2×1 骨牌鋪滿 3×N 矩形（N ≤ 30，偶數），求方案數。N 為奇數時答案為 0（面積為奇數無法鋪滿）。

狀態分析與遞推推導

考慮最右側的垂直分割線 L（不可切開骨牌）。L 到右邊界形成的「不可再分割」區塊，長度只能是 2 或 ≥4 的偶數。
長度 2 的不可分割塊有 3 種鋪法（三橫、左豎右兩橫、右豎左兩橫）。
長度 ≥4 的不可分割塊只有 2 種（鋸齒狀兩種對稱）。

設 f[n] 為 3×n 方案數。最右不可分割塊長度為 2,4,6,...,n，得：
f[n] = 3*f[n-2] + 2*f[n-4] + 2*f[n-6] + ... + 2*f[0] (1)
同理 f[n-2] = 3*f[n-4] + 2*f[n-6] + ... + 2*f[0] (2)
(1)-(2)：f[n] = 4*f[n-2] - f[n-4]。

初始值與計算

f[0]=1（空矩形 1 種），f[2]=3。
奇數項均為 0。
遞推計算至 f[30] 即可。

參考代碼（C++）

Nf[N]
01
23
411
641
8153
10571
122131

樣例輸入 2,8,12 → 輸出 3,153,2131，完全吻合。