题意分析

题目要求用$2 \times 1$的多米诺骨牌铺满一个$3 \times n$的矩形，计算不同的铺法数量。这是一个典型的动态规划问题，关键在于找出递推关系。

解题思路

1. 状态定义：

   • 定义$f(n)$为铺满$3 \times n$矩形的不同铺法数量。

2. 初始条件：

   • $f(0) = 1$：当$n = 0$时，只有一种铺法（不放置任何骨牌）。
   • $f(2) = 3$：当$n = 2$时，有三种基本铺法（全部竖放、上方横放两个下方竖放一个、下方横放两个上方竖放一个）。

3. 递推关系：

   • 对于$n \geq 4$且$n$为偶数，递推公式为$f(n) = 4 \times f(n - 2) - f(n - 4)$。
   • 推导基于铺法结构分析：每个$3 \times n$的铺法可由$3 \times (n - 2)$的铺法扩展，但需排除重复计数的情况。

4. 递推过程：

   • 由于骨牌是$2 \times 1$的，仅当$n$为偶数时可铺满，因此递推仅处理偶数。

代码解释

#include <iostream>
#include <cstring>
using namespace std;
int f[31];

int main()
{
    memset(f, 0, sizeof(f));
    f[0] = 1;  // 初始条件：n=0时有一种铺法
    f[2] = 3;  // 初始条件：n=2时三种铺法
    
    // 递推计算偶数n的铺法数
    for (int i = 4; i <= 30; i += 2) {
        f[i] = 4 * f[i - 2] - f[i - 4];  // 应用递推公式
    }

    int n;
    while (cin >> n && n != -1) {
        cout << f[n] << endl;  // 直接输出预处理结果
    }
    return 0;
}

注意事项

1. 输入处理：

   • 输入包含多个测试用例，以$-1$结束，直接查询预处理数组$f$得到结果。

2. 递推公式：

   • $f(n) = 4 \times f(n - 2) - f(n - 4)$是核心，通过分析铺法的扩展方式和去重推导得出。

3. 边界条件：

   • $n=0$是递推的基础，保证公式对$n \geq 2$的偶数有效。
   • 题目输入保证$n$为非负整数，无需处理奇数（奇数时无法铺满，结果为0，但题目未给出此类输入）。

复杂度分析

• 时间复杂度：预处理时间$O(15)$（仅计算$n=0, 2, 4, \dots, 30$共16个值），每次查询$O(1)$。
• 空间复杂度：$O(31)$，存储递推结果的数组空间。

该算法通过预处理所有可能的$n$值，实现了高效的常数时间查询，完全满足题目数据范围（$n \leq 30$）的要求。