LeetCode 1411. 给 N x 3 网格图涂色的方案数

2021-03-07 HGNULB 约 8 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1411. 给 N x 3 网格图涂色的方案数

题意分析

给定一个 $n$ 行 $3$ 列的网格，每个格子必须涂成红、黄、绿三色之一，要求任意两个相邻格子（上下或左右）颜色不同，问合法涂色方案总数，结果对 $10^9 + 7$ 取模。

列数被死死钉在 $3$，这是最强的信号：一行的合法涂法是一个可以完整枚举的小集合，而不是随 $n$ 增长的东西。行与行之间只通过「上下相邻不同色」耦合，也就是说第 $i$ 行的合法性只取决于第 $i-1$ 行，与更早的行无关——这正是逐行递推的前提。

另一条信号是要求取模且 $n$ 可达 $5000$。取模说明答案是指数级增长的计数量，不可能靠搜索枚举；$n = 5000$ 说明一个关于 $n$ 的线性递推就足够，甚至不需要矩阵快速幂。

边界只有一处：$n = 1$ 时不存在上下相邻约束，答案就是单行合法涂法的总数。这一行的数目要能自己数出来：第一格 $3$ 选，第二格与第一格不同有 $2$ 选，第三格与第二格不同有 $2$ 选，共 $12$ 种。

解法：按行模式分类 DP

核心思路

暴力做法是深搜每个格子的颜色，共 $3^{3n}$ 种组合，$n = 2$ 就已经上千，$n = 5000$ 毫无可能。稍好一点的做法是先枚举出单行的 12 种合法涂法，再定义 dp[i][s] 表示第 $i$ 行涂成第 $s$ 种模式的方案数，逐行做 $12 \times 12$ 的转移，总代价 $O(144n)$，能过但状态数偏冗余。

真正的观察是：这 12 种模式不需要区分到具体颜色。把一行的涂法按「首尾两格是否同色」分成两类——首尾相同的形如 ABA（如红黄红），首尾不同的形如 ABC（如红黄绿）。数一数：ABA 类中 A 有 3 选、B 有 2 选，共 $6$ 种；ABC 类是三色的全排列，共 $6$ 种；合计 12 种，与直接枚举一致。

分类的价值在于类内同质：任意一个 ABA 模式，其下一行能接的合法模式数量都一样，与它具体是哪三种颜色无关（因为三种颜色地位对称，任何一个 ABA 都能通过颜色置换变成另一个 ABA，而置换不改变可接后继的计数）。于是 12 个状态可以压缩成 2 个。

现在显式定义状态：sameEnds[i] 表示前 $i$ 行都合法、且第 $i$ 行是 ABA 型的方案数；allDiff[i] 表示前 $i$ 行都合法、且第 $i$ 行是 ABC 型的方案数。答案是 sameEnds[n] + allDiff[n]。

转移系数靠手工枚举一次得出。以上一行是 ABA 型、具体取 121（用 1/2/3 代表三色）为例，下一行三格分别不能等于 1, 2, 1，且自身左右相邻不同：合法的有 212, 213, 312, 232, 313——其中 ABA 型的是 212, 232, 313 共 $3$ 个，ABC 型的是 213, 312 共 $2$ 个。再以上一行是 ABC 型、取 123 为例，下一行合法的有 212, 231, 312, 232——ABA 型的是 212, 232 共 $2$ 个，ABC 型的是 231, 312 共 $2$ 个。

于是递推式为 sameEnds[i] = 3 * sameEnds[i-1] + 2 * allDiff[i-1]、allDiff[i] = 2 * sameEnds[i-1] + 2 * allDiff[i-1]，初值 sameEnds[1] = allDiff[1] = 6。注意 dp[i] 只依赖 dp[i-1]，所以两个滚动变量就够，不需要开数组。

解题步骤

把 sameEnds 与 allDiff 都初始化为 $6$，对应第一行的两类模式各 6 种。第一行没有上方约束，所以初值就是单行的纯计数结果；这一步同时把 $n = 1$ 的边界处理掉了——循环从 $i = 2$ 起，$n = 1$ 时一次都不进，直接返回 $6 + 6 = 12$。

从 $i = 2$ 循环到 $n$，每轮按上面两条递推式算出新的两个值。循环变量从 2 开始是因为初值代表的是第 1 行，每一轮把「已知第 $i-1$ 行的分类计数」推进到第 $i$ 行。

必须先把两个新值算进临时变量 nextSameEnds、nextAllDiff，再一起赋回。因为两条式子都用到旧的 sameEnds 和 allDiff，先赋值会让第二条式子读到已被覆盖的新值，这是滚动数组最经典的陷阱。

每一步都对 $10^9+7$ 取模。方案数增长约每行 5 倍，$n = 5000$ 时是天文数字；用 long 承接 3 * sameEnds + 2 * allDiff，两个乘数最大 $3 \times (10^9+6) \approx 3 \times 10^9$，相加不超过 $5 \times 10^9$，落在 long 范围内不会溢出，但若用 int 就会。

返回 (sameEnds + allDiff) % MOD，两类模式互斥且穷尽了第 $n$ 行的所有可能，直接相加即为总方案数。

以 $n = 3$ 走一遍：

初始（第 1 行）：sameEnds = 6，allDiff = 6，此时总方案 $12$，与 $n = 1$ 的答案吻合。
$i = 2$：nextSameEnds = 3 * 6 + 2 * 6 = 30，nextAllDiff = 2 * 6 + 2 * 6 = 24，赋回后 sameEnds = 30、allDiff = 24。总数 $54$，正是 $n = 2$ 的标准答案。
$i = 3$：nextSameEnds = 3 * 30 + 2 * 24 = 90 + 48 = 138，nextAllDiff = 2 * 30 + 2 * 24 = 60 + 48 = 108，赋回后 sameEnds = 138、allDiff = 108。
返回 $138 + 108 = 246$。

顺带验证转移方向没写反：若把 nextAllDiff 误写成 3 * sameEnds + 2 * allDiff，$n = 2$ 会算出 $30 + 30 = 60$，与已知的 $54$ 不符——用小规模答案反查系数是这类计数 DP 最快的自检手段。

代码实现

class Solution {
    public int numOfWays(int n) {
        final long MOD = 1_000_000_007L;
        // 第一行无上方约束，ABA 型与 ABC 型各 6 种。
        long sameEnds = 6;
        long allDiff = 6;

        for (int i = 2; i <= n; i++) {
            // 两条式子都读旧值，必须先算进临时变量再一起赋回。
            long nextSameEnds = (3 * sameEnds + 2 * allDiff) % MOD;
            long nextAllDiff = (2 * sameEnds + 2 * allDiff) % MOD;
            sameEnds = nextSameEnds;
            allDiff = nextAllDiff;
        }

        return (int) ((sameEnds + allDiff) % MOD);
    }
}

func numOfWays(n int) int {
    const mod int64 = 1_000_000_007
    // 第一行无上方约束，ABA 型与 ABC 型各 6 种。
    sameEnds, allDiff := int64(6), int64(6)

    for i := 2; i <= n; i++ {
        // 两条式子都读旧值，必须先算进临时变量再一起赋回。
        nextSameEnds := (3*sameEnds + 2*allDiff) % mod
        nextAllDiff := (2*sameEnds + 2*allDiff) % mod
        sameEnds = nextSameEnds
        allDiff = nextAllDiff
    }

    return int((sameEnds + allDiff) % mod)
}

复杂度分析

时间复杂度：$O(n)$。循环恰好执行 $n - 1$ 轮，每轮是四次乘法、两次加法和两次取模，全是常数操作。相比不分类的 $12 \times 12$ 转移，常数被压掉了两个数量级。

空间复杂度：$O(1)$。只用了 sameEnds、allDiff 和两个临时变量，因为第 $i$ 行只依赖第 $i-1$ 行，历史行的计数用完即弃，不需要开长度为 $n$ 的数组。

关键点总结

逐行 DP 的前提是「行间只通过相邻一行耦合」。看到网格题先确认依赖跨度：只依赖上一行就能滚动，依赖上两行就要留两组变量。

状态压缩的依据是等价类：若两个具体状态的后继计数完全相同，它们就可以合并成一个状态。本题靠颜色的对称性把 12 个模式压成 2 类，这是从「枚举状态」跃迁到「枚举状态的性质」的关键一步。

转移系数拿不准时，取一个具体代表手工枚举一遍，再用小规模答案（$n = 1$ 得 12、$n = 2$ 得 54）反查。计数 DP 的系数错误极难从代码上看出来，必须靠小样本校验。

滚动更新多个互相依赖的状态时，一律先算全部新值再统一赋回；就地覆盖是这类代码最高频的隐性错误。

面试视角：面试官会先让你写出 $12 \times 12$ 的朴素版本，再追问「能不能减少状态数」。答题时要主动说出「颜色是可置换的，所以只需区分首尾是否同色」，并当场推出四个系数 $3, 2, 2, 2$。如果面试官把 $n$ 提到 $10^{18}$，要能接上「两状态线性递推可以写成 $2 \times 2$ 矩阵，用快速幂做到 $O(\log n)$」。

更一般的列数 $m$ 需要做轮廓线状态压缩 DP，状态是整行的颜色序列；本题是 $m = 3$ 时人工完成了这个压缩，理解这层关系才能迁移。

易错点总结

就地更新覆盖旧值：写成 sameEnds = 3 * sameEnds + 2 * allDiff; 后紧跟 allDiff = 2 * sameEnds + 2 * allDiff;，$n = 2$ 会算出 sameEnds = 30、allDiff = 2*30 + 12 = 72，返回 $102$，正确答案是 $54$。

两类系数写反：把 allDiff 的转移写成 3 * sameEnds + 2 * allDiff，$n = 2$ 返回 $60$ 而非 $54$。

初值写成 sameEnds = 6, allDiff = 12（误把 12 当作 ABC 型数量）：$n = 1$ 直接返回 $18$，正确是 $12$。

循环从 $i = 1$ 开始：$n = 1$ 时多做一轮转移，返回 $30 + 24 = 54$，而正确答案是 $12$。

用 int 存中间结果：$n$ 较大时 3 * sameEnds 中 sameEnds 接近 $10^9$，乘 3 后约 $3 \times 10^9$ 超过 int 上限，结果变成负数，最终答案错误甚至为负。

只在最后取一次模：中间值在 $n$ 增大时爆 long，$n = 30$ 左右答案就已超过 $9 \times 10^{18}$，溢出后结果完全失真。

模数写成 1_000_000_009 或 998244353：$n = 5000$ 时答案与标准输出不同，且小样本（$n \le 10$）看不出差别，极难排查。

返回时忘记再取一次模：sameEnds + allDiff 两个都可能接近 $10^9+6$，相加约 $2 \times 10^9$，直接强转 int 会溢出成负数。

把「相邻」误解为只含左右不含上下：那样每行独立，答案会算成 $12^n$，$n = 2$ 得 $144$ 而非 $54$。

试图对 $n$ 用记忆化递归：$n = 5000$ 的递归深度会栈溢出，而本题的递推天然是自底向上的迭代形式。

相似题目

题目	难度	考察点
276. 栅栏涂色	中等	一维版本，状态按「与前一根是否同色」分两类，约束是不许三连同色
256. 粉刷房子	中等	同为逐行转移且相邻不同色，但求最小代价而非计数，状态需保留具体颜色
265. 粉刷房子 II	困难	颜色数扩展到 $k$，需维护每行最小与次小值把转移从 $O(k^2)$ 降到 $O(k)$
790. 多米诺和托米诺平铺	中等	同为按列轮廓分类的计数递推，状态是「边界凸出形态」而非颜色关系
91. 解码方法	中等	一维计数 DP，转移依赖前一位与前两位，考的是合法性判定而非状态等价类
198. 打家劫舍	中等	相邻互斥约束下的滚动 DP，两个变量滚动的写法与本题同构
62. 不同路径	中等	网格计数 DP 的入门形态，逐行滚动但无相邻冲突约束
1473. 粉刷房子 III	困难	在颜色维度外再加「街区数」维度，状态变三维，考多维状态设计