LeetCode 1411：网格涂色问题的动态规划解法

1. 问题背景与理解这道LeetCode题目1411. 给Nx3网格图涂色的方案数看似简单却蕴含着不少有趣的组合数学思想。题目要求我们计算用三种颜色给N行3列的网格涂色的方案数且相邻格子颜色不能相同。这里的相邻指的是上下左右四个方向的直接相邻。我第一次看到这个问题时以为就是个简单的排列组合题。但当我尝试用暴力枚举法解决时很快就发现随着N的增加计算量呈指数级增长。比如当N5时理论上有3^15种可能的涂法每个格子3种选择共15个格子直接枚举显然不现实。2. 基础解法分析2.1 小规模情况枚举让我们先从小规模的N开始分析。对于N1的情况即单行3列的网格第一个格子有3种选择第二个格子有2种选择不能与第一个相同第三个格子有2种选择不能与第二个相同所以总共有3×2×212种涂法。这与题目给出的示例一致。但当N2时情况就复杂多了。第二行的涂法不仅取决于自身的相邻格子还受第一行的影响。这时候我们就需要更系统的方法。2.2 状态转移思路这个问题非常适合用动态规划来解决。我们可以将每一行的涂色模式视为一个状态然后计算从一个状态转移到另一个状态的方案数。具体来说每一行的涂色模式可以分为两类ABC型三个格子颜色各不相同如红绿蓝ABA型两边的格子颜色相同中间的格子颜色不同如红绿红对于N1时ABC型有6种3种颜色排列ABA型有6种3种主色×2种中间色3. 动态规划解法实现3.1 状态定义与转移方程设dp_abc[n] 表示第n行是ABC型的方案数dp_aba[n] 表示第n行是ABA型的方案数初始条件dp_abc[1] 6dp_aba[1] 6转移方程一个ABC型的下一行可以是2种ABC型如红绿蓝→绿红绿、绿蓝绿2种ABA型如红绿蓝→绿红蓝、绿蓝红一个ABA型的下一行可以是2种ABC型如红绿红→绿红绿、绿蓝绿3种ABA型如红绿红→绿红绿、绿蓝绿、蓝绿蓝因此转移方程为 dp_abc[n] 2 * dp_abc[n-1] 2 * dp_aba[n-1] dp_aba[n] 2 * dp_abc[n-1] 3 * dp_aba[n-1]3.2 Java实现代码public int numOfWays(int n) { if (n 0) return 0; long abc 6; // ABC型 long aba 6; // ABA型 long mod 1000000007; for (int i 2; i n; i) { long new_abc (2 * abc 2 * aba) % mod; long new_aba (2 * abc 3 * aba) % mod; abc new_abc; aba new_aba; } return (int)((abc aba) % mod); }3.3 复杂度分析时间复杂度O(N)因为我们只需要进行N次迭代计算空间复杂度O(1)只使用了常数个变量存储状态4. 数学优化与矩阵快速幂4.1 状态转移的矩阵表示我们可以将状态转移表示为矩阵乘法[abc_n] [2 2][abc_{n-1}] [aba_n] [2 3][aba_{n-1}]这意味着我们可以使用矩阵快速幂来将时间复杂度优化到O(logN)。4.2 矩阵快速幂实现final int MOD 1000000007; public int numOfWays(int n) { if (n 0) return 0; if (n 1) return 12; long[][] transition {{2, 2}, {2, 3}}; long[][] result matrixPower(transition, n - 1); long abc 6, aba 6; long total (result[0][0] * abc result[0][1] * aba) % MOD; total (total (result[1][0] * abc result[1][1] * aba) % MOD) % MOD; return (int)total; } private long[][] matrixPower(long[][] matrix, int power) { long[][] result {{1, 0}, {0, 1}}; // 单位矩阵 while (power 0) { if ((power 1) 1) { result multiplyMatrix(result, matrix); } matrix multiplyMatrix(matrix, matrix); power 1; } return result; } private long[][] multiplyMatrix(long[][] a, long[][] b) { long[][] res new long[2][2]; for (int i 0; i 2; i) { for (int j 0; j 2; j) { res[i][j] (a[i][0] * b[0][j] a[i][1] * b[1][j]) % MOD; } } return res; }5. 边界条件与注意事项5.1 大数处理由于结果可能非常大当N5000时结果约为1e2000量级题目要求对结果取模1000000007。在实现时需要注意使用long类型存储中间结果避免int溢出每次运算后立即取模而不是最后才取模矩阵乘法中的乘法操作可能导致中间结果溢出需要及时取模5.2 初始条件当N0时应该返回0因为没有格子需要涂色。这是一个容易被忽略的边界条件。5.3 测试用例验证建议测试以下情况N1 → 12N2 → 54N3 → 246N7 → 106494N5000 → 302282146. 扩展思考6.1 更一般的m×n网格如果问题扩展到m×n网格m不固定为3解法会有什么变化这种情况下状态数会随着m的增加而急剧增加对于m列状态数约为3×2^(m-1)。对于较大的m可能需要更复杂的动态规划方法或状态压缩技巧。6.2 颜色数量的变化如果题目改为使用k种颜色而不是3种解法需要如何调整初始的ABC型和ABA型的数量会变化ABC型k×(k-1)×(k-2)ABA型k×(k-1)转移方程中的系数也需要相应调整。6.3 实际应用场景这类问题在实际中有多种应用平面地图着色问题电路板布线设计日程安排中的冲突避免图形学中的纹理生成7. 个人解题心得在解决这个问题时我最初尝试了暴力回溯法很快就遇到了性能瓶颈。通过分析小规模案例我发现了状态分类的规律。动态规划的解法虽然高效但推导状态转移方程需要仔细分析所有可能的情况。矩阵快速幂的优化是一个惊喜它将线性时间复杂度降低到了对数级。这提醒我在解决类似问题时可以考虑是否存在数学上的优化空间。一个容易犯的错误是忽略了模运算的时机。我在第一次提交时只在最后做了取模结果中间计算就溢出了。正确的做法是在每次运算后都立即取模。