覆盖墙壁

题意

用 2x1 砖和 L 形三格砖覆盖 2 x N 的墙壁，砖可以旋转，问覆盖方案数的最后四位。

思路

这是经典的 2 x N 铺砖递推。设 dp[n] 表示覆盖 2 x n 墙壁的方案数。

初始：

text

1
2
3dp[0] = 1
dp[1] = 1
dp[2] = 2

对 n >= 3，递推为：

text

1dp[n] = 2 * dp[n-1] + dp[n-3]

题目只要求最后四位，所以每次递推后对 10000 取模即可。

小 DP 表

n	0	1	2	3	4
dp[n]	1	1	2	5	11

题面也给出 2x3 有 5 种覆盖方法，与表格一致。

Python 知识

用列表保存 dp，递推时直接按下标访问前三项。
% 10000 保留最后四位。
输出时不用补前导零，直接 print(dp[n])。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18MOD = 10000

n = int(input())

if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2

    for length in range(3, n + 1):
        dp[length] = (2 * dp[length - 1] + dp[length - 3]) % MOD

    print(dp[n])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1000005];

int main() {
    cin >> n;
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % 10000;
    cout << dp[n] << endl;
    return 0;
}

复杂度

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。也可以滚动数组优化到 $O(1)$ 。

总结

这题重点是识别铺砖递推，并且从一开始就按题目要求保留最后四位，避免大数增长。

目录

题意

思路

小 DP 表

Python 知识

代码

复杂度

总结