HDU 2501 題解：鋪瓷磚——線性遞推

題目大意

用 2×1 的小矩形鋪滿 2×N 的大矩形，求方案數。遞推公式：f[n] = f[n-1] + 2*f[n-2]，f[0]=0, f[1]=1, f[2]=3。

遞推推導

• 最後一列豎放一塊 → 剩下 2×(n-1) → f[n-1] 種。
• 最後兩列橫放兩塊 → 剩下 2×(n-2) → f[n-2] 種。
• 最後兩列形成一個 2×2 的方塊（兩種擺法） → 剩下 2×(n-2) → 2*f[n-2] 種。

合併得 f[n] = f[n-1] + 2*f[n-2]。

AC 代碼

#include <iostream>
using namespace std;

const int N = 40;
long long f[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    f[0] = 0; f[1] = 1; f[2] = 3;
    for (int i = 3; i < N; ++i)
        f[i] = f[i-1] + 2 * f[i-2];

    int n;
    cin >> n;
    while (n--) {
        int m;
        cin >> m;
        cout << f[m] << '\n';
    }
    return 0;
}

複雜度

• 預處理 O(N)，查詢 O(1)。
• 空間 O(N)。