ZeroJudge 解題筆記：n129.p1. 鋪磁磚問題

作者：王一哲
日期：2026年8月28日


ZeroJudge 題目連結：n129.p1. 鋪磁磚問題

解題想法

題目只給一個整數 $n$，代表地板的總面積為 $1 \times n$，有 3 種可以用的地板面積 $1 \times 1$、$1 \times 2$、$1 \times 3$，要回傳組成長度 $n$ 的所有方法數。這題考無限背包，開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表地板總長度為 $i$ 的方法數。但是題目要找的是排列方法數，外層 for 迴圈要跑地板總長度 $1$ 到 $n$，內層的 for 迴圈跑可以用的地板長度 $1、2、3$，最後答案在 $dp[n]$。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

n = int(input())  # 地板 1*n
dp = [0] * (n+1)  # 組成地板長度 i 的方法數
dp[0] = 1  # 長度 0 方法數 1
for j in range(1, n+1):  # 這題是排列，要先跑長度
    for p in range(1, 4):  # 三種地板長度 1, 2, 3
        if j >= p: dp[j] += dp[j - p]
print(dp[n])

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.9 MB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 地板 1*n
    vector<long long> dp (n+1, 0);  // 組成地板長度 i 的方法數
    dp[0] = 1;  // 長度 0 方法數 1
    for(int j = 1; j <= n; j++) {  // 這題是排列，要先跑長度
        for(int p = 1; p <= 3; p++) {  // 三種地板長度 1, 2, 3
            if (j >= p) dp[j] += dp[j - p];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

使用時間約為 1 ms，記憶體約為 1.6 MB，通過測試。

#include <cstdio>

int main() {
    int n; scanf("%d", &n);  // 地板 1*n
    long long dp[72] = {0};  // 組成地板長度 i 的方法數，題目限制 n 最大為 71
    dp[0] = 1;  // 長度 0 方法數 1
    for(int j = 1; j <= n; j++) {  // 這題是排列，要先跑長度
        for(int p = 1; p <= 3; p++) {  // 三種地板長度 1, 2, 3
            if (j >= p) dp[j] += dp[j - p];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

C 語言程式碼

使用時間約為 1 ms，記憶體約為 1.6 MB，通過測試。

#include <stdio.h>

int main() {
    int n; scanf("%d", &n);  // 地板 1*n
    long long dp[72] = {0};  // 組成地板長度 i 的方法數，題目限制 n 最大為 71
    dp[0] = 1;  // 長度 0 方法數 1
    for(int j = 1; j <= n; j++) {  // 這題是排列，要先跑長度
        for(int p = 1; p <= 3; p++) {  // 三種地板長度 1, 2, 3
            if (j >= p) dp[j] += dp[j - p];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}