题目
你有一个 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 表示,合法的行模式只有两类:


