题目
你有一个 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
题目分析
第一种方法，先考虑暴力搜索，枚举每个格子涂哪种颜色。
第二种方法，可以找到规律：
这个涂色问题的答案满足一个递推公式：
f(n) = 5 × f(n-1) - 2 × f(n-2)
其中：
f(1) = 12f(2) = 54f(3) = 5×54 - 2×12 = 270 - 24 = 246f(4) = 5×246 - 2×54 = 1122- ……
为了能让这个公式从 n=2 开始算，我们人为定义一个 f(0) = 3（它没有实际意义，只是为了公式成立）。
验证一下：
f(2) = 5×f(1) - 2×f(0) = 5×12 - 2×3 = 60 - 6 = 54✅
方法一：状态压缩记忆化搜索
采用 DFS+ 记忆化的方法，从下往上逐格涂色：
- 状态表示：
(i, j)表示当前正在涂第 i 行第 j 列preRow表示下一行（i+1 行）的颜色状态（用 6 位二进制表示）curRow表示当前行已涂色的状态
- 状态转移：
- 每个格子尝试三种颜色
- 需要检查：不能与下方格子颜色相同，不能与左侧格子颜色相同
- 使用位运算高效地存储和检查颜色状态
- 记忆化优化：
- 将 (i, j, preRow, curRow) 压缩为一个整数作为 key
- 避免重复计算相同状态
方法二：数学递推公式
关键观察：每行只有两种模式
由于每行只有 3 个格子，且左右不能同色，我们可以枚举所有合法的单行涂色方式。
用三种颜色 A、B、C 表示，合法的行模式只有两类：