点击获取AI摘要

1931. 用三种不同颜色为网格涂色 H

给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大，返回对 10⁹ + 7 取余的结果。

示例 1：

colorthegrid

输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。

示例 2：

copy-of-colorthegrid

输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。

示例 3：

输入：m = 5, n = 5
输出：580986

提示：

1 <= m <= 5
1 <= n <= 1000

问题分析

给定 m×n 的网格（1 ≤ m ≤ 5，1 ≤ n ≤ 1000），每个格子都要用三种颜色之一（红/绿/蓝）上色，且要求 无两相邻格子颜色相同。邻接关系包括水平方向（左右）和垂直方向（上下）。

由于 m 较小（至多 5），可以把“同一列的 m 个格子”看作一个整体状态。对于一列内部，必须保证上下相邻的颜色不同；对于两列之间，必须保证同一行的两个格子颜色不同。

算法思路

1. 合法列状态数

对于一列，逐格向下涂色：
- 第一行格子有 3 种颜色可选；
- 之后每增加一格，颜色只能是剩下的 2 种（不能与上一格相同）；
因此一列共有 $3 \times 2^{,m-1}$ 种合法的“列颜色方案”。
当 m=5 时，合法状态数 $=3×2^4=48$ ；当 m=1 时，合法状态数 $=3$ ；依此类推。

我们可以把每个“列方案”用长度为 m 的元组（或一个整数掩码）来表示。例如：若 m=3，用 (0,1,2) 表示第一行红、第二行绿、第三行蓝。然后预先枚举出全部合法的列状态列表 states。

2. 列与列之间的兼容性

若列 A 和列 B 在同一行颜色相同，则它们不能相邻摆放。
因此，对所有合法状态对 $(s_i, s_j)$ ，检查：

$\forall\,0\le r<m:\; s_i[r] \ne s_j[r].$
枚举时可得到一个邻接列表（邻接矩阵／邻接表）compat[i] 记录状态 i 能与哪些状态 j 配对。

3. 动态规划

定义 $\text{dp}[c][i]$ 为第 $c$ 列选择状态 $i$ 时的方案总数。

初始化 $c=1$ 时：对于任意合法状态 $i$ ， $\text{dp}[1][i]=1$ 。
状态转移（ $2\le c\le n$ ）：

$\text{dp}[c][j] = \sum_{\substack{i=0\\ i\,\text{与}\,j\,\text{兼容}}}^{S-1} \text{dp}[c-1][i].$
最终答案 $=\sum_{i=0}^{S-1}\text{dp}[n][i] \bmod (10^9+7)$ 。
其中 $S=3\times2^{m-1}$ 是合法列状态数。

时间复杂度

预处理列状态：枚举每个长度为 m 的染色情况，共 $3^m$ 种，筛选出 $S=3\times2^{m-1}$ 个合法；时间约 $O(3^m \times m)$ ，当 m≤5 时常数小（最多 3^5=243）；
预处理兼容矩阵：两两枚举 $S\times S$ 对，检查 m 行是否同色；时间 $O(S^2 \times m)$ ，当 m=5 时 $S=48$ ，约 48^2×5≈11520 步；
动态规划：共 n 列，每列从上一列的兼容状态中累加，时间 $O(n \times S_{\mathrm{avg\_neighbors}})$ $O (n \times S_{avg_neighbors})$ 。最坏的邻居数约 $S$ $S$ ，则 $O(nS^2)$ $O (n S^{2})$ 。
- 当 m=5, S=48, S^2≈2304, n≤1000 时，总步数 ≈2.3×10^6，完全可行。
空间：若保存整个 dp 表，为 $O(nS)$ ；也可以用滚动数组仅保留上一列，总空间 $O(S)$ 。

若 n 更大（例如 n 接近 10⁹ ），可以把兼容关系矩阵看作 $S×S$ 的转移矩阵，用矩阵快速幂将 $n$ 次转移压缩为 $O(S^3\log n)$ 。在本题 n≤1000 的规模下，直接DP已足够高效。

经测试，时间复杂度为 $O(M * 2^M * N)$

代码分解

用整数 0/1/2 表示三种颜色；
枚举所有合法的“列状态”，存入 states；
构造每对状态是否兼容的布尔矩阵 compatible；
用一维滚动数组实现 DP，依次累加；
返回最终总和。

代码实现

DFS 枚举合法单列

用 dfs_build(0, -1) 从 row=0 开始，prev_color=-1 表示第一行可任意选择 0/1/2；
每往下一行，只要不与上一行 (prev_color) 相等即可；
递归深度为 m，结束时将当前路径 tuple(path) 加入 states。
最终 states 列表长度应 $3\times2^{m-1}$ 。

兼容性检查

compatible[i][j] 表示第 i 种列状态能否在左侧，第 j 种列状态能否在右侧；
遍历 states[i] 与 states[j] 每一行，若有任何一行相同，则标记不兼容。
时间复杂度 $O(S^2 \times m)$ ，当 m=5, S=48 时约 48^2×5≈11520 步。

动态规划

定义 dp_prev[i] 为“上一列选状态 i 时的方案数”；初始时第一列“任意状态”都记为 1；
对于第 col(≥2) 列，枚举 j 作为当前列状态，累加所有 i（上一列）满足 compatible[i][j] 的 dp_prev[i]；
用 %MOD 保证不溢出；更新完一列后，用滚动数组交换指针（dp_prev, dp_cur = dp_cur, [0]*S）。

合并答案

第 n 列计算完毕后，所有 dp_prev[i] 即为“第 n 列状态为 i” 的方案数，直接求和取模。

class Solution:
    MOD = 10**9 + 7

    def colorTheGrid(self, m: int, n: int) -> int:
        # 1. 枚举所有合法的列状态
        #    用整数列表表示，如 [0, 1, 2, 0, ...]，其中 0/1/2 代表三种颜色。
        states = []
        def dfs_build(col, prev_color):
            """
            通过深度优先搜索构建单列的所有合法方案。
            col: 当前处理到哪一行（0-based）
            prev_color: 上一行的颜色（若为 -1 则表示第一行）
            path: 当前已选颜色列表
            """
            if col == m:
                # 到达第 m 行，保存当前路径
                states.append(tuple(path))
                return
            for color in (0, 1, 2):
                if color != prev_color:
                    path.append(color)
                    dfs_build(col + 1, color)
                    path.pop()

        path = []
        dfs_build(0, -1)
        S = len(states)  # 合法状态总数，应=3 * 2^(m-1)

        # 2. 构造兼容性矩阵：若两列同一行颜色都不相等，便兼容
        compatible = [[True] * S for _ in range(S)]
        for i in range(S):
            for j in range(S):
                # 检查 states[i] 和 states[j] 是否在每一行都不同色
                for row in range(m):
                    if states[i][row] == states[j][row]:
                        compatible[i][j] = False
                        break

        # 3. 动态规划（滚动数组）仅保留上一列的 dp
        #    dp_prev[i] = 以第 c-1 列状态 i 的方案数；dp_cur[i] = 以第 c 列状态 i 的方案数
        dp_prev = [1] * S   # 第一列每个状态方案数 = 1
        dp_cur = [0] * S

        for _ in range(2, n + 1):
            # 每次计算第 col 列
            for j in range(S):
                total = 0
                for i in range(S):
                    if compatible[i][j]:
                        total += dp_prev[i]
                dp_cur[j] = total % self.MOD
            # 滚动：更新上一列数组
            dp_prev, dp_cur = dp_cur, [0] * S

        # 4. 累加最后一列所有状态方案数并取模
        return sum(dp_prev) % self.MOD

优化：用“状态压缩 + 枚举”的方式 预先把所有合法的“列状态”编码成整数（或元组），并且针对每个状态只保存它“可以搭配”的那些邻居状态索引（邻接表）。这样在 DP 转移时，就不用再二次校验“state[i] 和 state[j] 是否兼容”，只需遍历邻接表即可，能把常数因子大幅度缩小。

DP 部分使用一维滚动数组，每一步只遍历合法邻居列表，减少无效分支判断。

将 % MOD 的操作尽量放在最内层，并把一些全局变量（如 MOD、状态总数 S）局部化，减少属性/全局访问开销。

经过测试，时间复杂度为 $O(M^N)$

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        MOD = 10**9 + 7

        # -----------------------------------------------------------
        # 1. 枚举“单列”所有合法的涂色情况，把它们编码成整数索引 0..S-1
        #    例如：m=3 时，可能的合法列状态共有 3 * 2^(m-1) = 12 个。
        #    我们把每个状态都生成一个元组（长度为 m，值为 0/1/2），并保存在 list states 中。
        #    最后再把它们按顺序编号：state_id 0..S-1。
        #    这样后面可以直接用索引访问、构造邻接表。
        # -----------------------------------------------------------
        states = []
        path = []

        def dfs_build(col: int, prev_color: int):
            # col : 当前要填到第几行（0-based）
            # prev_color: 上一行填的是什么颜色（若为 -1，表示还没填，即当前处于第一行）
            if col == m:
                # path 长度正好等于 m，且满足相邻不同色，记录一个合法状态
                states.append(tuple(path))
                return
            # 枚举三种颜色
            for c in (0, 1, 2):
                if c != prev_color:
                    path.append(c)
                    dfs_build(col + 1, c)
                    path.pop()

        dfs_build(0, -1)
        # 合法状态总数
        S = len(states)
        # states[i] 就是第 i 个合法状态，对应一个长度 m 的 0/1/2 元组
        # 这个 S 一定等于 3 * 2^(m-1)。当 m=5 时，S=48；m=1 时，S=3；以此类推。

        # -----------------------------------------------------------
        # 2. 构造“邻接表”：对每一个状态 i，预先把所有与之“列间颜色都不同”的 j 放到 adj[i] 里
        #    这样 DP 转移时，直接遍历 adj[i]，而不用再在循环里做兼容性判断。
        #    兼容条件：对所有 0 <= row < m，states[i][row] != states[j][row]
        # -----------------------------------------------------------
        adj = [[] for _ in range(S)]
        for i in range(S):
            si = states[i]
            for j in range(S):
                sj = states[j]
                # 检查 si 和 sj 对应行是否都不相同
                ok = True
                for row in range(m):
                    if si[row] == sj[row]:
                        ok = False
                        break
                if ok:
                    adj[i].append(j)

        # -----------------------------------------------------------
        # 3. 动态规划（滚动数组）
        #    dp_prev[i] 表示：上一列（第 c-1 列）选状态 i 时的方案数
        #    dp_cur[i]  表示：当前列 （第 c   列）选状态 i 时的方案数
        #
        #    初始条件 (c=1)：第 1 列任何状态都可以，记为 1。
        #    转移 (c -> c+1)：dp_cur[j] = sum{ dp_prev[i] | i in adj[j] } % MOD
        #    最后答案 = sum(dp_prev[i] for i in 0..S-1) % MOD
        #
        #    关键优化点在于：我们 **只遍历 adj[j]** 而不是所有 i，再去判断兼容与否，
        #    从 O(S^2 * m) 的常数提到 O(Σ|adj[j]|)，非常节省时间。
        # -----------------------------------------------------------
        dp_prev = [1] * S   # c=1 的时候，每个状态 i 都只有一种选择
        dp_cur = [0] * S

        # 从第 2 列开始，依次做转移
        for _ in range(2, n + 1):
            # 遍历“本列”可能的状态 j
            for j in range(S):
                s = 0
                # 只遍历可以跟 j 配对的 i 列表
                for i in adj[j]:
                    s += dp_prev[i]
                # 取模后写入
                dp_cur[j] = s % MOD

            # 滚动：把当前列当作下一轮的“上一列”
            dp_prev, dp_cur = dp_cur, [0] * S

        # 累加最后一列所有状态的方案数
        ans = sum(dp_prev) % MOD
        return ans