LC790. 多米诺和托米诺平铺 domino-and-tromino-tiling
LC790. 多米诺和托米诺平铺 domino-and-tromino-tiling
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。
返回对 10^9 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1
输出: 1
提示：
1 <= n <= 1000
题意
这一题就算你知道是 dp，解出来也有一定的难度。
题目到底是什么意思？
做什么
我们要用：
2×1 的竖砖；
1×2 的横砖；
L 形的 tromino（占三个格子的 L）。
去完全覆盖 2×n 的棋盘。（高度恒为2）
转移方程定义
想得到递推公式，我们必须要找到规律。
转移方程含义
dp[n] //棋盘完全铺满 ✅
p[n] //棋盘右边多出一个缺角 ⚠️符号约定：
⬜️ → 空白格
⬛️ → 已有砖块（不关心类别）
🟫 → 竖砖块
🟦 → 横砖块
🟧 → L 形砖块完整状态 dp 的三种来源
A-最右边放一个竖砖
占据最右边一列。剩下的棋盘长度 n-1 完全铺满，方案数：dp[n-1]。
⬛️⬛️ ... ⬛️ 🟫
⬛️⬛️ ... ⬛️ 🟫B-最右边放两个横砖
占据最右边两列 2×2（每个横砖占 1×2）。剩下长度 n-2 的棋盘已铺好, 方案数：dp[n-2]
⬛️⬛️ ... ⬛️ 🟦🟦
⬛️⬛️ ... ⬛️ 🟦🟦C-最右边放 L 形砖
L 形砖旋转两种方向。放完后右边形成“缺角”状态，剩下的长度 n-1 的棋盘是 p[n-1]。方案数贡献：2 * p[n-1]
方向1（右上缺角）：
⬛️⬛️ ... 🟧⬜️
⬛️⬛️ ... 🟧🟧方向2（右下缺角）：
⬛️⬛️ ... 🟧🟧
⬛️⬛️ ... 🟧⬜️PS: 缺角要放在右边，这样后续才可能通过 L 补全。
综合得到递归公式
dp[i] = dp[i-1] + dp[i-2] + 2 * p[i-1]别急，p 数组怎么来的？
缺角状态 p 的两种来源
A-从缺角状态延伸一列竖砖（缺角继续存在）上缺角延续，来自 p[i-1]
以前：
⬛️⬛️ ... ⬛️⬜️
⬛️⬛️ ... ⬛️⬛️放一块竖着的：
🟫⬛️⬛️ ... ⬛️⬜️
🟫⬛️⬛️ ... ⬛️⬛️PS: 因为对称，方便理解，我们把新的竖放在左边。
B-从完整状态放一个 L，制造出新的缺角。来自 dp[i-2]
从完整变缺角（上缺）：
⬛️⬛️ ... ⬛️🟧⬜️
⬛️⬛️ ... ⬛️🟧🟧或（下缺）：
⬛️⬛️ ... ⬛️🟧🟧
⬛️⬛️ ... ⬛️🟧⬜️所以
p[i] = p[i-1] + dp[i-2]实现
搞清楚了上面的过程，解法就可以写了。
class Solution {
public int numTilings(int n) {
long MOD = 1000000007L;
long[] dp = new long[n + 1];
long[] p = new long[n + 1];
dp[0] = 1;
dp[1] = 1;
p[0] = 0;
p[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] + 2 * p[i - 1]) % MOD;
p[i] = (p[i - 1] + dp[i - 2]) % MOD;
}
return (int) dp[n];
}
}为什么不是最后统一 MOD？
会溢出，就算是 long 也不行。
为什么可以每一步都 MOD?
因为模运算满足加法和乘法的分配律：
(a + b) % M = ((a % M) + (b % M)) % M
(a * b) % M = ((a % M) * (b % M)) % M所以无论何时取模，只要在每步都保持 % M，最终结果与“最后取模”是数学等价的。
但由于计算机的“有限精度”，提前取模是防止爆掉的工程必要手段。
效果
1ms 击败 58.21%
反思
各种角度而言，这一题其实不能说一个中等题。
而是思维上的难题。
v2-空间压缩
思路
同样的，dp 和 p 都是只关心上 2 个变量
我们可以对数组压缩
实现
class Solution {
public int numTilings(int n) {
long MOD = 1000000007L;
long dp0 = 1;
long dp1 = 1;
long p0 = 0;
long p1 = 0;
for (int i = 2; i <= n; i++) {
long dpTemp = (dp1 + dp0 + 2 * p1) % MOD;
long pTemp = (p1 + dp0) % MOD;
// 更新
dp0 = dp1;
dp1 = dpTemp;
p0 = p1;
p1 = pTemp;
}
return (int) dp1;
}
}效果
0ms 100%