(经典dp) I型 L型 铺盖2*n

前言

既然是都是经典dp了，那各个平台的标题和描述难免有些差异

各平台

吐槽一句，作为一道非常经典的dp，2022蓝桥杯初赛直接题面都不编一下故事就拿来考了

洛谷：P1990 覆盖墙壁

力扣：790. 多米诺和托米诺平铺

蓝桥杯：积木画 “蓝桥杯”练习系统

等等平台

题面描述

用1*2的I型和三个单位的L型铺盖2*n的取余，求方案数

下图来自力扣

这两玩意还有专门的名称多米诺和托米诺

长度为3时的所有情况

题解

正常分析前缀和

暴力枚举前几个情况总结规律 推荐题解：找不到规律？请看图！0x3f

个人的分析解释，可能有点玄学

定义dp[n]表示到第i个位置，正好能平铺的方案数

---

• 考虑最后放的是1*2的I型

  • 竖着放1个 dp[i - 1]
  • 横着放2个 dp[i - 2]

• 考虑最后放L型

L型的链接边必须放在最右侧，单个点放于左侧和左侧的突出点链接

L型的摆放具有对称性，因此只考虑一种情况最后*2即可

核心： 左侧区域至少也要有一个L型来进行缺口的补充 (即上图的情况45)

两个L型拼接占用长度为3

解释1：

# 中间补充奇数个1*2
# i-4
▢▢▣▣
▢◉◉▣
# i-6
▢▢◉◉▣▣
▢◉◉◉◉▣

# 中间补充偶数个1*2
# i-3
▢▣▣
▢▢▣
# i-5
▢◉◉▣▣
▢▢◉◉▣

# 综上 从i-3到0的所有可能叠加
# 即 i-3的前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解释2

有点玄学

# 本质是用一个突出的点来拟合最右侧的L
▣▣
◉▣
# 这个点必须伴随左侧有一个L的提供 因此长度至少是i-3
▢▣▣
▢▢▣
# 将拟合点的作用分配给前面i-3的每个位置上
# 累计所有情况，前缀和
1
2
3
4
5
6
7
8

const int mod = 1e9 + 7;
const int M = 10 + 1000;

long long dp[M];
long long pre[M];

int __init__ = []() {
    // 0长度也是一种情况
    dp[0] = 1, dp[1] = 1, dp[2] = 2;
    pre[0] = 1, pre[1] = 2, pre[2] = 4;
    for (int i = 3; i < M; i += 1) {
        dp[i] = (dp[i - 1] + dp[i - 2] + 2 * pre[i - 3]) % mod;
        pre[i] = (pre[i - 1] + dp[i]) % mod;
    }
    return 0;
}();

class Solution {
public:
    int numTilings(int n) {
        return (int)::dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

普通线性dp表示

有些朋友直接列举前几项情况，玄学般的得出结论

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

其实就是将前缀和化简通向公式

① dp[n] = dp[n - 1] + dp[n - 2] + 2 * (dp[n - 3] + ... + 1)
② dp[n - 1] = dp[n - 2] + dp[n - 3] + 2 * (dp[n - 4] + ... + 1)
① - ② => dp[n] = 2 * dp[n - 1] + dp[n - 3];
1
2
3

const int mod = 1e9 + 7;
const int M = 10 + 1000;

long long dp[M];

int __init__ = []() {
// ① dp[n] = dp[n - 1] + dp[n - 2] + 2 * (dp[n - 3] + ... + 1)
// ② dp[n - 1] = dp[n - 2] + dp[n - 3] + 2 * (dp[n - 4] + ... + 1)
// ① - ② => dp[n] = 2 * dp[n - 1] + dp[n - 3];
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < M; i += 1) {
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
    }
    return 0;
}();

class Solution {
public:
    int numTilings(int n) {
        return (int)::dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

状态机dp

放一张力扣官方的题解图

将问题的情况进行广义化

原题问的是最后一列铺满的情况

我们考虑所有情况进行广义化

共四种情况

• 最后一列 空
• 最后一列 上方一个点
• 最后一列 下方一个点
• 最后一列 铺满

---

定义 dp[][4] 表示第i个位置处于状态j (i位置前是铺满态)

上图的正方形有点迷惑性，直接展示了一个正方形，我们关心的是最后一列

考虑对第i列作用，并且使得第i-1正好补全

---

思维坑：为什么不要dp[i][0] += dp[i-1][0] 放一个I

# 若 dp[i][0] += dp[i-1][0] 放一个I
# 则可表示为下面的状态

# 放置前(准备放)
i-2 i-1 i
 ▣  空  空
 ▣  空  空
# 放置后(完成放置)
i-2 i-1 i
 ▣  ▣  空
 ▣  ▣  空

# 看似完成了，但这里的实质是对i-1的操作，不符合我们对dp[][4]的定义
# 换一种思路，这种情况已经在dp[i-1][3]中考虑了
1
2
3
4
5
6
7
8
9
10
11
12
13
14

const int mod = 1e9 + 7;
const int M = 10 + 1000;

// 表示第i-1位前全铺满
// 第i位所处的状态的种类
// 0 空
// 1 上点
// 2 下点
// 3 满
long long dp[M][4];

int __init__ = []() {
    // i-1状态全满，则第0的状态处理视为满的
    dp[0][3] = 1;
    for (int i = 1; i < M; i += 1) {
        // 空则 前满+不操作
        dp[i][0] = dp[i - 1][3];
        // 上点 前空+L 前下点+一
        dp[i][1] = dp[i - 1][0] + dp[i - 1][2];
        // 下点 前空+L 前上点+一
        dp[i][2] = dp[i - 1][0] + dp[i - 1][1];
        // 满 前空+二 前满+I 前上点+L 前下点+L
        dp[i][3] = dp[i - 1][0] + dp[i - 1][3] + dp[i - 1][1] + dp[i - 1][2];
        for (int j = 0; j < 4; j += 1) {
            dp[i][j] %= mod;
        }
    }
    return 0;
}();

class Solution {
public:
    int numTilings(int n) {
        return (int)::dp[n][3];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

---

---

END