LeetCode 题解工作台
用三种不同颜色为网格涂色
给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。 涂色方案需要满足： 不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 10 9 + 7 取余 的结果…
1
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们注意到，网格的行数不超过 ，那么一列中最多有 种不同的颜色方案。 因此，我们定义 表示前 列中，第 列的涂色状态为 的方案数。状态 由 $f[i - 1][k]$ 转移而来，其中 是第 $i - 1$ 列的涂色状态，且 和 满足不同颜色相邻的要求。即：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。
涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 109 + 7 取余 的结果。
示例 1：
输入：m = 1, n = 1 输出：3 解释：如上图所示，存在三种可能的涂色方案。
示例 2：
输入：m = 1, n = 2 输出：6 解释：如上图所示，存在六种可能的涂色方案。
示例 3：
输入：m = 5, n = 5 输出：580986
提示：
1 <= m <= 51 <= n <= 1000
解题思路
方法一：状态压缩 + 动态规划
我们注意到，网格的行数不超过 ，那么一列中最多有 种不同的颜色方案。
因此，我们定义 表示前 列中，第 列的涂色状态为 的方案数。状态 由 转移而来，其中 是第 列的涂色状态，且 和 满足不同颜色相邻的要求。即：
其中 表示状态 的所有合法前驱状态。
最终的答案即为 的总和，其中 是任意合法的状态。
我们注意到， 只和 有关，因此我们可以使用滚动数组优化空间复杂度。
时间复杂度 ，空间复杂度 。其中 和 分别是网格的行数和列数。
class Solution:
def colorTheGrid(self, m: int, n: int) -> int:
def f1(x: int) -> bool:
last = -1
for _ in range(m):
if x % 3 == last:
return False
last = x % 3
x //= 3
return True
def f2(x: int, y: int) -> bool:
for _ in range(m):
if x % 3 == y % 3:
return False
x, y = x // 3, y // 3
return True
mod = 10**9 + 7
mx = 3**m
valid = {i for i in range(mx) if f1(i)}
d = defaultdict(list)
for x in valid:
for y in valid:
if f2(x, y):
d[x].append(y)
f = [int(i in valid) for i in range(mx)]
for _ in range(n - 1):
g = [0] * mx
for i in valid:
for j in d[i]:
g[i] = (g[i] + f[j]) % mod
f = g
return sum(f) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(3^{2m} \cdot n) |
| 空间 | O(3^{2m}) |
面试官常问的追问
外企场景- question_mark
Focus on the bitmask-based state transition approach for solving this problem.
- question_mark
Test if the candidate can handle the modulo operation correctly when dealing with large results.
- question_mark
Look for an understanding of dynamic programming and how to optimize it with state transitions.
常见陷阱
外企场景- error
Forgetting to use modulo 10^9 + 7 for the result, leading to overflow errors.
- error
Incorrectly representing column colorings as bitmasks, which can lead to invalid transitions.
- error
Not efficiently handling state transitions, which could result in a time complexity that exceeds limits.
进阶变体
外企场景- arrow_right_alt
Adjust the grid size (m or n) to test scalability of the solution.
- arrow_right_alt
Change the number of colors to see how the algorithm adapts to more complex cases.
- arrow_right_alt
Explore a version where no adjacent cells can share the same color diagonally.