---

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

• 标签：动态规划
• 难度：困难

题目链接

• 1411. 给 N x 3 网格图涂色的方案数 - 力扣

题目大意

描述：给定一个 $n \times 3$ 的网格图，用三种颜色涂色，要求相邻格子颜色不同。相邻定义为上下左右。

要求：返回涂色方案数。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le n \le 5000$。

示例：

• 示例 1：

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

• 示例 2：

输入：n = 2
输出：54

解题思路

思路 1：状态 DP

1. 核心思想

每一行只有 $3$ 列，可能的颜色模式有限。每行只能由两种类型的模式构成：

• ABC 型：三种颜色都不同，如 012, 021, 102 等。相邻列颜色不同。
• ABA 型：三种颜色中只有两种出现，且第一列和第三列相同，如 010, 101, 202 等。

2. 状态转移

对于一行，考虑与上一行的关系：

• ABC 型（$3!=6$ 种）：
  • 下一行是 ABC 型：如果要上下相邻也不同，排列方式有有限种。
  • 下一行是 ABA 型：类似。
• ABA 型（$3 \times 2 = 6$ 种）：
  • 下一行是 ABC 型或 ABA 型。

经过分析，转移关系如下：

• ABC 型可以转移到相同类型：$2$ 种（例如 012 可以转到 201 或 120）。
• ABC 型可以转移到 ABA 型：$2$ 种（例如 012 转到 101 或 202）。
• ABA 型可以转移到 ABC 型：$2$ 种（例如 010 转到 201 或 102）。
• ABA 型可以转移到相同类型：$3$ 种（例如 010 转到 101、202 或 020... 实际更复杂，需要严格枚举）。

实际已知结论（可以严密枚举证明）：

• 令 $dp\_abc[i]$ 表示第 $i$ 行是 ABC 型时的方案数，$dp\_aba[i]$ 表示第 $i$ 行是 ABA 型时的方案数。
• $dp\_abc[i] = 2 \times dp\_abc[i-1] + 2 \times dp\_aba[i-1]$
• $dp\_aba[i] = 2 \times dp\_abc[i-1] + 3 \times dp\_aba[i-1]$

3. 初始条件

$dp\_abc[1] = 6$（三种颜色的所有排列）
$dp\_aba[1] = 6$（三色选两种，再排列使首尾相同：$C(3,2) \times 2 = 6$）

答案 = $(dp\_abc[n] + dp\_aba[n]) \mod MOD$。

4. 举例说明

以 $n=1$ 为例：$6+6=12$ 种。
以 $n=2$ 为例：$dp\_abc[2] = 2\times6+2\times6=24$，$dp\_aba[2]=2\times6+3\times6=30$，共 $54$。

思路 1：代码

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        abc, aba = 6, 6  # 第一行
        for _ in range(2, n + 1):
            abc, aba = (2 * abc + 2 * aba) % MOD, (2 * abc + 3 * aba) % MOD
        return (abc + aba) % MOD

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。