T1411.给N x 3 网格图涂色的方案

dfs, dp, Matrix Exponentiation, https://leetcode.cn/problems/number-of-ways-to-paint-n-3-grid/

你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：n = 1
输出：12
解释：总共有 12 种可行的方法：

示例 2：

输入：n = 2
输出：54

示例 3：

输入：n = 3
输出：246

示例 4：

输入：n = 7
输出：106494

示例 5：

输入：n = 5000
输出：30228214

提示：

n == grid.length
grid[i].length == 3
1 <= n <= 5000

使用 记忆化搜索（Memoized DFS） 结合 状态压缩（Bitmask） 的技巧来解决问题。相较于数学推导（ABA/ABC模式），这种方法更通用，通过模拟逐个格子填色的过程来计数。

python

MOD = 1_000_000_007


# (i, j)：当前位置
# pre_row：上一行（i+1 行）的颜色
# cur_row：当前这一行已填入的颜色
@cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, j: int, pre_row: int, cur_row: int) -> int:
    if i == 0:  # 所有格子都已涂色
        return 1  # 找到一个合法方案

    if j == 3:  # i 行已涂色
        # 开始对 i-1 行涂色，cur_row 变成 pre_row
        return dfs(i - 1, 0, cur_row, 0)

    res = 0
    for color in range(3):  # 尝试给当前格子 (i, j) 填入 0, 1, 2 三种颜色

        # 冲突检查：

        # 1. 垂直冲突检查 (和 i+1 行对比)
        # if pre_row: 确保这不是第一行（n行没有上一行，pre_row初始为0）
        # color == pre_row >> (j * 2) & 3: 取出上一行同列的颜色进行对比
        vertical_conflict = (pre_row and color == (pre_row >> (j * 2) & 3))

        # 2. 水平冲突检查 (和 i 行 j-1 列对比)
        # if j: 确保这不是第 0 列（第 0 列左边没有格子）
        # color == cur_row >> ((j - 1) * 2) & 3: 取出当前行左边格子的颜色对比
        horizontal_conflict = (j and color == (cur_row >> ((j - 1) * 2) & 3))

        if vertical_conflict or horizontal_conflict:
            continue  # 颜色冲突，跳过，尝试下一种颜色

        # 递归调用：
        # 处理当前行的下一列 (j + 1)
        # 将当前颜色写入 cur_row 状态中：cur_row | (color << (j * 2))
        res += dfs(i, j + 1, pre_row, cur_row | (color << (j * 2)))

    return res % MOD


class Solution:
    def numOfWays(self, n: int) -> int:
        return dfs(n, 0, 0, 0)  # 从最后一行开始涂色

下面是对代码的详细深度解读：
1. 核心概念：状态压缩 (Bitmask)
代码中没有使用数组来存一行的颜色，而是用一个整数（pre_row 和 cur_row）来表示一行 3 个格子的颜色状态。
颜色：题目有红黄绿 3 种颜色，可以用数字 0, 1, 2 表示。
二进制：数字 0, 1, 2 最多只需要 2 个比特位（00, 01, 10）。
压缩：一行有 3 个格子，每个格子占 2 位，一共只需要 $3 \times 2 = 6$ 个比特位就能存下一行的所有颜色信息。
第 0 列的颜色存放在二进制的第 0-1 位。
第 1 列的颜色存放在二进制的第 2-3 位。
第 2 列的颜色存放在二进制的第 4-5 位。
位运算操作解释：
color << (j * 2)：将当前颜色移位到第 j 列对应的位置。
cur_row | ...：将移位后的颜色“写入”当前行的状态中。
state >> (j * 2) & 3：将第 j 列的颜色移位到最低端，并用 & 3（二进制 11）取出最后两位，即读取第 j 列的颜色。
2. 函数参数详解
python
def dfs(i: int, j: int, pre_row: int, cur_row: int) -> int:
i (int): 当前正在处理的行号（倒序，从 n 处理到 1）。表示还剩 i 行没有涂完。
j (int): 当前正在处理的列号（0, 1, 2）。
pre_row (int): 上一行（也就是物理上的第 i+1 行）的颜色状态。因为我们要检查垂直相邻冲突，所以需要知道上一行的颜色。
cur_row (int): 当前行（第 i 行）已经填好的颜色状态。用于传递给下一列，以及最终传递给下一层递归。
3. 代码逻辑逐行解析
终止条件与换行
python
    if i == 0:  # 所有行（n行）都处理完毕
        return 1  # 找到了一种合法的全图涂色方案
python
    if j == 3:  # 当前行（第 i 行）的 3 个格子都填完了
        # 准备处理下一行（i-1 行）
        # 列号重置为 0
        # 当前行 cur_row 变成了下一行的 "pre_row"
        # 下一行的 cur_row 初始化为 0
        return dfs(i - 1, 0, cur_row, 0)
核心循环与剪枝
python
    res = 0
    for color in range(3):  # 尝试给当前格子 (i, j) 填入 0, 1, 2 三种颜色
        
        # 冲突检查：
        
        # 1. 垂直冲突检查 (和 i+1 行对比)
        # if pre_row: 确保这不是第一行（n行没有上一行，pre_row初始为0）
        # color == pre_row >> (j * 2) & 3: 取出上一行同列的颜色进行对比
        vertical_conflict = (pre_row and color == (pre_row >> (j * 2) & 3))
        
        # 2. 水平冲突检查 (和 i 行 j-1 列对比)
        # if j: 确保这不是第 0 列（第 0 列左边没有格子）
        # color == cur_row >> ((j - 1) * 2) & 3: 取出当前行左边格子的颜色对比
        horizontal_conflict = (j and color == (cur_row >> ((j - 1) * 2) & 3))

        if vertical_conflict or horizontal_conflict:
            continue  # 颜色冲突，跳过，尝试下一种颜色

        # 递归调用：
        # 处理当前行的下一列 (j + 1)
        # 将当前颜色写入 cur_row 状态中：cur_row | (color << (j * 2))
        res += dfs(i, j + 1, pre_row, cur_row | (color << (j * 2)))
    
    return res % MOD
4. 为什么这个解法有效？（优缺点）
优点：
直观：这就是一个标准的“回溯/DFS”逻辑：填一个格子 -> 检查合不合法 -> 填下一个。
通用性强：如果题目改成 $N \times M$ ( $M$ 较小)，或者颜色数量变成 4 种，这个模板改改就能用。而数学推导（ABA/ABC）需要重新推公式。
关键点 - @cache： 如果不加 @cache，这就是纯暴力的指数级回溯，肯定会超时。加上 @cache 后，这就变成了记忆化搜索（等价于自顶向下的动态规划）。
状态 (i, pre_row) 决定了剩余行的填法数量。
虽然函数签名里有 j 和 cur_row，但实际上在缓存中，跨行的状态复用主要依赖于 i 和 pre_row。当 j=0 时，状态只有 (i, 0, pre_row, 0)，这大大减少了计算量。
与数学DP解法（ABA/ABC）的对比：
数学DP：时间复杂度 $O (N)$ ，空间 $O (1)$ 。利用了 $3$ 列的特殊性归纳出了公式。
记忆化DFS：时间复杂度 $O (N \times 3^{3})$ （因为每一行有 $3^{3} = 27$ 种状态，实际合法状态更少），本质上是在构建状态机。虽然比数学公式慢一点点，但对于 $N = 5000$ 依然是瞬间完成的。
总结
这段代码是非常经典的轮廓线DP / 状态压缩DP的简化写法。它通过位运算巧妙地避开了数组操作的开销，并通过记忆化搜索解决了重复子问题。

这是一个经典的动态规划问题。我们需要找出给 $N \times 3$ 网格涂色的方案数，且满足相邻格子颜色不同。

解题思路

分类讨论单行状态：对于任意一行（有3个格子），因为有3种颜色可选，且相邻格子颜色不能相同，我们可以将合法的涂色方案分为两类：
- ABA模式：第一格颜色和第三格颜色相同（但与第二格不同）。
  - 例如：红-黄-红，绿-红-绿。
  - 对于单行， $N = 1$ 时，第一格有3种选择，第二格有2种（不能同第一格），第三格只能有1种（必须同第一格）。
  - ABA类初始数量： $3 \times 2 \times 1 = 6$ 种。
- ABC模式：第一格、第二格、第三格颜色互不相同。
  - 例如：红-黄-绿，绿-红-黄。
  - 对于单行， $N = 1$ 时，第一格有3种选择，第二格有2种，第三格有1种（不能同第一格，也不能同第二格）。
  - ABC类初始数量： $3 \times 2 \times 1 = 6$ 种。
所以在 $N = 1$ 时，总方案数为 $6 + 6 = 12$ 。
状态转移：当我们从第 $i - 1$ 行推导第 $i$ 行时，需要考虑上一行的模式对当前行模式的影响（垂直方向颜色不能相同）。
- 如果第 $i - 1$ 行是 ABA 模式（例如 0-1-0）：
  - 第 $i$ 行如果是 ABA 模式（例如 x-y-x）：通过穷举发现有 3 种合法的涂色方案。
  - 第 $i$ 行如果是 ABC 模式（例如 x-y-z）：通过穷举发现有 2 种合法的涂色方案。
- 如果第 $i - 1$ 行是 ABC 模式（例如 0-1-2）：
  - 第 $i$ 行如果是 ABA 模式：通过穷举发现有 2 种合法的涂色方案。
  - 第 $i$ 行如果是 ABC 模式：通过穷举发现有 2 种合法的涂色方案。
递推公式：设 typeA 为当前行为 ABA 模式的方案数，typeB 为当前行为 ABC 模式的方案数。下一行的方案数 new_typeA 和 new_typeB 计算如下：
- new_typeA = typeA * 3 + typeB * 2
- new_typeB = typeA * 2 + typeB * 2
计算结果：从 $N = 2$ 循环到 $N$ ，最后返回 (typeA + typeB) % MOD。

Python 代码实现

python

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 初始化 N=1 时的状态
        # typeA: ABA 模式的数量 (例如: 红黄红) -> 6种
        # typeB: ABC 模式的数量 (例如: 红黄绿) -> 6种
        typeA, typeB = 6, 6
        
        # 从第2行开始迭代计算到第n行
        for _ in range(n - 1):
            # 计算下一行的方案数
            # 下一行是 ABA 模式的来源：
            # 1. 上一行是 ABA，有 3 种涂法变成 ABA
            # 2. 上一行是 ABC，有 2 种涂法变成 ABA
            new_typeA = (typeA * 3 + typeB * 2) % MOD
            
            # 下一行是 ABC 模式的来源：
            # 1. 上一行是 ABA，有 2 种涂法变成 ABC
            # 2. 上一行是 ABC，有 2 种涂法变成 ABC
            new_typeB = (typeA * 2 + typeB * 2) % MOD
            
            # 更新状态
            typeA, typeB = new_typeA, new_typeB
            
        return (typeA + typeB) % MOD

复杂度分析

时间复杂度： $O (N)$ ，需要循环 $N - 1$ 次。
空间复杂度： $O (1)$ ，只使用了几个变量存储当前状态。

这个问题可以通过动态规划（Dynamic Programming）来高效解决。
核心思路
对于每一行 $1 \times 3$ 的网格，满足“相邻颜色不同”的涂色方案只有两种基本模式：
ABA 型：第一列和第三列颜色相同，中间颜色不同（例如：红-黄-红）。
ABC 型：三列颜色各不相同（例如：红-黄-绿）。
1. 计算第一行（ $n = 1$ ）的初始方案数
ABA 型：第一格有 3 种选法，第二格有 2 种（不能与第一格相同），第三格必须与第一格相同（1 种）。 $3 \times 2 \times 1 = 6$ 种。
ABC 型：第一格 3 种，第二格 2 种，第三格 1 种（不能与前两格相同）。 $3 \times 2 \times 1 = 6$ 种。
总计： $6 + 6 = 12$ 种。
2. 推导状态转移方程
假设第 $i - 1$ 行的涂色方案已知，我们考虑第 $i$ 行如何涂色以不违反相邻规则（水平和垂直）：
如果第 $i - 1$ 行是 ABA 型（假设是 红-黄-红）：
下一行可以是 ABA 型：黄-红-黄、黄-绿-黄、绿-红-绿（3 种）。
下一行可以是 ABC 型：黄-红-绿、绿-红-黄（2 种）。
结论： $A B A_{i} = 3 \times A B A_{i - 1} + 2 \times A B C_{i - 1}$
如果第 $i - 1$ 行是 ABC 型（假设是 红-黄-绿）：
下一行可以是 ABA 型：黄-红-黄、绿-红-绿（2 种）。
下一行可以是 ABC 型：黄-绿-红、绿-红-蓝（注：实际上是 2 种，如 2-3-1 和 3-1-2）（2 种）。
结论： $A B C_{i} = 2 \times A B A_{i - 1} + 2 \times A B C_{i - 1}$
3. 算法实现
由于 $N$ 最大为 5000，我们可以直接使用 $O (N)$ 的迭代。如果 $N$ 非常大，也可以使用题目提到的矩阵快速幂优化到 $O (\log N)$ 。
Python 代码实现
python
class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 初始状态 (n=1)
        # aba: 模式如 1-2-1 的数量
        # abc: 模式如 1-2-3 的数量
        aba = 6
        abc = 6
        
        # 从第 2 行开始迭代到第 n 行
        for _ in range(n - 1):
            # 根据递推公式计算新一行的数量
            # 注意需要使用旧值计算，所以先存入临时变量
            next_aba = (3 * aba + 2 * abc) % MOD
            next_abc = (2 * aba + 2 * abc) % MOD
            
            aba, abc = next_aba, next_abc
            
        return (aba + abc) % MOD
复杂度分析
时间复杂度： $O (N)$ ，只需遍历一次 $n$ 。
空间复杂度： $O (1)$ ，只使用了常数个变量存储中间状态。
矩阵快速幂 (扩展)
如果需要处理 $N > 10^{9}$ 的情况，可以使用如下转移矩阵：
$(\begin{matrix} A B A_{n} \\ A B C_{n} \end{matrix}) = {(\begin{matrix} 3 & 2 \\ 2 & 2 \end{matrix})}^{n - 1} (\begin{matrix} 6 \\ 6 \end{matrix})$
通过矩阵快速幂，可以在对数时间内求得结果。对于本题 $N = 5000$ ，线性递推已足够高效。

矩阵快速幂（Matrix Exponentiation）解法。

代码实现的逻辑回顾

初始状态 ( $n = 1$ )：
- ABA 模式（首尾颜色相同）：6 种
- ABC 模式（三个颜色不同）：6 种
递推关系：
- New_ABA = 3 * Old_ABA + 2 * Old_ABC
- New_ABC = 2 * Old_ABA + 2 * Old_ABC
矩阵化： $[\begin{matrix} 3 & 2 \\ 2 & 2 \end{matrix}]$
目标：计算矩阵的 $n - 1$ 次方，然后乘以初始的 12 种方案。

Python 代码 (加注释版)

python

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

        # 定义 2x2 矩阵乘法函数
        # C = A * B
        def multiply(A, B):
            # 初始化一个 2x2 的全 0 矩阵
            C = [[0, 0], [0, 0]]
            for i in range(2):
                for k in range(2):
                    # 矩阵乘法核心：行 x 列
                    if A[i][k] == 0: continue # 简单剪枝（可选）
                    for j in range(2):
                        C[i][j] += A[i][k] * B[k][j]
                        C[i][j] %= MOD
            return C

        # 1. 构造转移矩阵 M
        # [ 3, 2 ]  -> 对应 ABA 的递推系数
        # [ 2, 2 ]  -> 对应 ABC 的递推系数
        M = [[3, 2], [2, 2]]

        # 2. 初始化结果矩阵 res 为单位矩阵 I (对角线为1，其余为0)
        # 任何矩阵乘以单位矩阵，结果不变。这相当于数字乘法里的 "1"
        res = [[1, 0], [0, 1]]

        # 3. 我们需要计算 M 的 (n-1) 次方
        # 因为 n=1 时不需要递推，直接返回初始值
        exp = n - 1

        # 4. 矩阵快速幂算法 (Binary Exponentiation)
        # 时间复杂度 O(log n)
        while exp > 0:
            # 如果指数 current 的最后一位是 1 (奇数)
            # 则将当前的底数矩阵乘入结果中
            if exp & 1:
                res = multiply(res, M)
            
            # 底数矩阵自乘 (M -> M^2 -> M^4 ...)
            M = multiply(M, M)
            
            # 指数右移一位 (相当于除以2)
            exp >>= 1

        # 5. 计算最终结果
        # 此时 res 存储的是 M^(n-1)
        # 设 res = [[a, b], [c, d]]
        # 最终 ABA 数量 = (a * 6) + (b * 6)
        # 最终 ABC 数量 = (c * 6) + (d * 6)
        # 总方案数 = 6 * (a + b + c + d)
        
        # 求矩阵 res 所有元素之和
        sum_res = sum(res[0]) + sum(res[1])
        
        return (sum_res * 6) % MOD

复杂度分析

时间复杂度: $O (\log N)$
- 矩阵大小是固定的 $2 \times 2$ ，视为常数 $C$ 。
- 快速幂循环执行 $\log_{2} (N)$ 次。
- 总计算量极小，即使 $N = 10^{18}$ 也能瞬间算出。
空间复杂度: $O (1)$
- 只存储了几个 $2 \times 2$ 的矩阵变量。

为什么这个解法是“降维打击”？

DP解法 ( $O (N)$ ) 需要一步步算：第1行 -> 第2行 -> ... -> 第n行。
快速幂解法 ( $O (\log N)$ ) 像是拥有了“传送门”。
- 它不关心中间第 500 行、第 501 行具体是多少。
- 它利用数学结合律，把 $M \times M \times . . . \times M$ 合并计算，直接“跳跃”到第 $n$ 行。
- 这是解决线性递推问题（如斐波那契数列、爬楼梯、铺砖块）在大数据范围下的标准最优解。

T1411.给N x 3 网格图涂色的方案 ​

T1411.给N x 3 网格图涂色的方案