LeetCode 1411：给 N x 3 网格图涂色的方案数
1. 题目介绍
LeetCode 1411 题“给 N x 3 网格图涂色的方案数”(Number of Ways to Paint N × 3 Grid) 是一道典型的动态规划 (Dynamic Programming) 问题。
题目要求
用 3 种颜色涂满 n×3 网格，要求任何相邻（上下或左右）的格子颜色都不能相同，找出所有合法方案数。
2. 解题思路
2.1 问题简化：单行分析
解决这个问题的关键在于找出“行与行”之间的递推关系。首先，我们将问题简化，只分析单行 (1×3) 的情况。
在遵守“左右相邻格子颜色不同”的规则下，一行 3 个格子的颜色组合模式主要可以分为两类：
- ABC 类：三个格子颜色全不同（用了 3 种颜色），例如：红-绿-蓝
- ABA 类：两边的格子颜色相同（只用了 2 种颜色），例如：红-绿-红
2.2 单行方案数计算
ABC 类（三色）
- 第 1 个格子：有 3 种选择
- 第 2 个格子：有 2 种选择（不能和第 1 个同色）
- 第 3 个格子：只有 1 种选择（不能和前两个同色）
- 总方案数：3×2×1=6 种
ABA 类（双色）
- 第 1 个格子：有 3 种选择
- 第 2 个格子：有 2 种选择（不能和第 1 个同色）
- 第 3 个格子：只有 1 种选择（必须和第 1 个同色）
- 总方案数：3×2×1=6 种
因此，单行总共有 6+6=12 种合法方案。
3. 动态规划状态定义
我们定义两个状态变量：
- An：第 n 行是 *ABC 类* 的方案数
- Bn：第 n 行是 *ABA 类* 的方案数
4. 状态转移方程推导
4.1 状态转移规律分析
通过具体例子分析，我们可以得到以下状态转移规律：
| 上一行状态 | 下一行变成 ABC (三色) | 下一行变成 ABA (双色) |
|---|---|---|
| ABC 类 (Ai) | 生成 2 个 | 生成 2 个 |
| ABA 类 (Bi) | 生成 2 个 | 生成 3 个 |
4.2 状态转移方程
根据上述规律，我们可以推导出状态转移方程：
- 下一行是 ABC 类：
Ai+1 = 2×Ai + 2×Bi - 下一行是 ABA 类：
Bi+1 = 2×Ai + 3×Bi
5. 初始状态
当 n=1 时：
- A1 = 6（ABC 类方案数）
- B1 = 6（ABA 类方案数）
6. 最终结果
第 n 行的总方案数为第 n 行所有合法情况的总和：
Totaln = An + Bn
7. 代码实现
7.1 注意事项
- 大数处理：由于 n 最大可以达到 5000，方案数会以指数级增长，需要对结果取余（通常取 1e9+7）
- 旧值保存：在更新状态时，需要保存旧值，避免覆盖后影响后续计算
7.2 C++ 代码实现
class Solution {
public:
int numOfWays(int n) {
long long a = 6, b = 6; // n=1 时的初始值 (ABC:6, ABA:6)
int mod = 1e9 + 7;
for (int i = 2; i <= n; i++) {
// 用临时变量 t 保存旧的 a 值，防止被覆盖
long long t = a;
// 更新 a (ABC 类): 公式 2*A + 2*B
a = (2 * t + 2 * b) % mod;
// 更新 b (ABA 类): 公式 2*A + 3*B
// 注意这里使用的是旧值 t
b = (2 * t + 3 * b) % mod;
}
// 最后记得再次取余
return (a + b) % mod;
}
};
8. 算法复杂度分析
- 时间复杂度：O(n)，只需要遍历一次到 n
- 空间复杂度：O(1)，只使用了几个变量
9. 总结
LeetCode 1411 题是一道典型的动态规划问题，通过以下步骤解决：
- 将问题简化为单行分析，识别出两种核心状态
- 计算单行的方案数，确定初始状态
- 推导状态转移方程，建立行与行之间的联系
- 实现代码，注意大数处理和旧值保存
- 计算最终结果，返回总方案数
这个解法体现了动态规划的核心思想：将复杂问题分解为简单子问题，通过状态定义和状态转移方程逐步求解。