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

约 4 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 阿里
标签
动态规划

题目描述

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

image-20260928225901325

image-20260928225901335

题意分析

用三种颜色给 n 行、3 列的网格涂色，左右相邻和上下相邻的格子都不能同色，统计所有合法方案并对 10^9+7 取模。

新一行只与上一行相邻，更早各行的具体颜色不影响这一行的选择。因此可以按行动态规划，再利用颜色之间的对称性压缩状态。

解法：按行模式分类 DP

核心思路

[!blue]

一行只有三个格子，左右相邻必须不同，所以合法行恰好分为两类：首尾相同的 ABA，以及三个颜色都不同的 ABC。A、B、C 表示互不相同的颜色。第一行没有上方约束，两类分别有 3×2 = 6 和 3×2×1 = 6 种。

设 sameEnds 是已经涂完若干行、最后一行属于 ABA 类的完整网格方案数，allDiff 是最后一行属于 ABC 类的方案数。只要上一行类型相同，就能通过颜色重命名互相转换，接到下一行两种类型的数量也分别相同，因此不必区分每个具体配色。

转移系数要同时满足同行和上下限制，可以固定上一行的颜色名称来推导：

  • 上一行是 ABA，下一行也首尾相同：首尾不能选 A。若选 B，中间可选 A 或 C；若选 C，中间只能选 A，共 3 种。
  • 上一行是 ABA，下一行三色不同：中间不能选 B。若选 A，两端可把 B、C 按两种顺序放置；若选 C，两端必须使用 A、B，其中的 A 会与上方冲突，所以共 2 种。
  • 上一行是 ABC，下一行首尾相同：首尾既不能选 A，也不能选 C，只能选 B；中间可选 A 或 C，共 2 种。
  • 上一行是 ABC，下一行三色不同：第一格若选 B，后两格只能是 C、A；第一格若选 C，后两格只能是 A、B，共 2 种。

因此下一行的两类总数为 nextSameEnds = 3×sameEnds + 2×allDiff，nextAllDiff = 2×sameEnds + 2×allDiff。每个新网格都有唯一的上一行前缀和新加的一行，按这两部分计数不会遗漏或重复。

两个新状态都算完并取模后，再一起替换旧状态。最后一行必然属于两类之一，将它们相加取模就是答案。

解题步骤

  1. 将第一行的两类方案数都初始化为 6。
  2. 从第 2 行开始，用上一行的两类计数计算两个新状态。
  3. 乘加使用 Java long 或 Go int64，取模后再更新 sameEnds 和 allDiff。
  4. 处理到第 n 行，返回两类计数之和对模数的余数。n = 1 时无需转移，直接得到第一行的总数。

代码实现

class Solution {
    public int numOfWays(int n) {
        final long MOD = 1_000_000_007L;

        // 第一行没有上方约束，ABA 与 ABC 两类各有六种具体模式。
        long sameEnds = 6;
        long allDiff = 6;

        for (int i = 2; i <= n; i++) {

            // 下一行首尾相同的方案：旧 ABA 各接三种，旧 ABC 各接两种。
            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 两类各有六种具体模式。
    sameEnds, allDiff := int64(6), int64(6)

    for i := 2; i <= n; i++ {

        // 下一行首尾相同的方案：旧 ABA 各接三种，旧 ABC 各接两种。
        nextSameEnds := (3*sameEnds + 2*allDiff) % mod
        // 两个新状态都读取上一行旧计数，不能提前覆盖。
        nextAllDiff := (2*sameEnds + 2*allDiff) % mod
        sameEnds = nextSameEnds
        allDiff = nextAllDiff
    }

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

复杂度分析

  • 时间复杂度：$O(n)$。每一行只计算两个状态，各需要常数次乘加。
  • 空间复杂度：$O(1)$。只保存上一行和下一行的两类计数。

关键点总结

[!green]

  • 状态保存的是整个已涂网格的方案数，分类依据只是最后一行的配色类型。
  • 能压缩为两类，是因为同类具体配色接到每个后继类的数量都一致。
  • 转移系数来自上下不冲突的配色数量，不能把每行的 12 种选择独立相乘。
  • 每次乘加和最终求和都取模，乘加前使用足够宽的整数。

易错点总结

[!yellow]

  • 只检查同行相邻颜色，会漏掉上下相邻限制，得到错误的独立乘法计数。
  • 先覆盖 sameEnds 再计算 allDiff，会把新旧两行的计数混在一起。
  • 将每个状态初始化为 1，会遗漏同一类型下的六种具体颜色安排。
  • 即使旧状态已经取模，乘以系数再相加仍可能超过 32 位整数范围，不能先用 int 算完再转宽类型。

相似题目

题目 难度 关联与区别
1931. 用三种不同颜色为网格涂色 困难 原题把固定三列推广为更一般窄网格，可枚举行状态并检查相邻行兼容性。
256. 粉刷房子 中等 同样限制相邻颜色不同，本题还要同时检查同行与上下行，而不是只有一维相邻关系。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/53728246
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！