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

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 个格子的颜色组合模式主要可以分为两类：

1. ABC 类：三个格子颜色全不同（用了 3 种颜色），例如：红-绿-蓝
2. 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. 动态规划状态定义

我们定义两个状态变量：

• A**n：第 n 行是 ABC 类 的方案数
• B**n：第 n 行是 ABA 类 的方案数

4. 状态转移方程推导

4.1 状态转移规律分析

通过具体例子分析，我们可以得到以下状态转移规律：

上一行状态	下一行变成 ABC (三色)	下一行变成 ABA (双色)
ABC 类 (A**i)	生成 2 个	生成 2 个
ABA 类 (B**i)	生成 2 个	生成 3 个

4.2 状态转移方程

根据上述规律，我们可以推导出状态转移方程：

1. 下一行是 ABC 类：
   A**i+1 = 2×A**i + 2×B**i

2. 下一行是 ABA 类：
   B**i+1 = 2×A**i + 3×B**i

5. 初始状态

当 n=1 时：

• A1 = 6（ABC 类方案数）
• B1 = 6（ABA 类方案数）

6. 最终结果

第 n 行的总方案数为第 n 行所有合法情况的总和：

Total**n = A**n + B**n

7. 代码实现

7.1 注意事项

1. 大数处理：由于 n 最大可以达到 5000，方案数会以指数级增长，需要对结果取余（通常取 1e9+7）
2. 旧值保存：在更新状态时，需要保存旧值，避免覆盖后影响后续计算

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*Ba = (2 * t + 2 * b) % mod;// 更新 b (ABA 类): 公式 2*A + 3*B// 注意这里使用的是旧值 tb = (2 * t + 3 * b) % mod;}// 最后记得再次取余return (a + b) % mod;}
};

8. 算法复杂度分析

• 时间复杂度：O(n)，只需要遍历一次到 n
• 空间复杂度：O(1)，只使用了几个变量

9. 总结

LeetCode 1411 题是一道典型的动态规划问题，通过以下步骤解决：

1. 将问题简化为单行分析，识别出两种核心状态
2. 计算单行的方案数，确定初始状态
3. 推导状态转移方程，建立行与行之间的联系
4. 实现代码，注意大数处理和旧值保存
5. 计算最终结果，返回总方案数

这个解法体现了动态规划的核心思想：将复杂问题分解为简单子问题，通过状态定义和状态转移方程逐步求解。