HDU 重建希望小學：3×n 地磚鋪設方案數 (線性遞推)

題目模型

教室 3×n，磚塊 1×1 和 2×2。求鋪設方案數。n≤30。

遞推關係

設 `f[n]` 為 3×n 方案數。
考慮最右側列狀態，可推導：`f[n] = f[n-1] + 2*f[n-2]` (n≥3)，
初始 `f[1]=1`, `f[2]=3`。
驗證：`f[3]=f[2]+2*f[1]=3+2=5` (符合樣例)。

代碼實現

#include 
long long f[31];
int main() {
    f[1]=1; f[2]=3;
    for(int i=3;i<=30;i++) f[i]=f[i-1]+2*f[i-2];
    int C,n; scanf("%d",&C);
    while(C--) { scanf("%d",&n); printf("%lld\n",f[n]); }
    return 0;
}

參考

queuelovestack 詳細推導