解题思路

用 1×1、1×2、1×3 的骨牌铺满 1×n 的方格，问有多少种铺法。

思路：递推。

看最后一块骨牌怎么放：

• 最后放 1×1：前面 n-1 格有 f(n-1) 种铺法
• 最后放 1×2：前面 n-2 格有 f(n-2) 种铺法
• 最后放 1×3：前面 n-3 格有 f(n-3) 种铺法

所以 f(n) = f(n-1) + f(n-2) + f(n-3)

初始：

• f(1) = 1（只能放 1×1）
• f(2) = 2（放 1×1+1×1 或 1×2）
• f(3) = 4（放三个1×1、1×1+1×2 等）

为什么要用 long long？ n 最大 50，铺法数增长很快，会超过 int 范围。

参考代码

#include <iostream>
using namespace std;

int main() {
    long long a = 1, b = 2, c = 4, x, n;
    cin >> n;

    if (n == 1) {
        cout << 1;
    } else if (n == 2) {
        cout << 2;
    } else if (n == 3) {
        cout << 4;
    } else {
        for (int i = 4; i <= n; i++) {
            x = a + b + c;  // f(n) = f(n-1)+f(n-2)+f(n-3)
            a = b;
            b = c;
            c = x;
        }
        cout << x << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，递推 n 次
• 空间复杂度：O(1)