标签: 动态规划
难度: Hard
你有一个 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.lengthgrid[i].length == 31 <= n <= 5000运行时间: 33 ms
内存: 16.0 MB
class Solution:
def numOfWays(self, n: int) -> int:
a, b = 6, 6
for _ in range(n-1):
a, b = (3*a+2*b) % 1000000007, (2*a+2*b) % 1000000007
return (a+b) % 1000000007
此题解采用动态规划的方法解决问题。首先，对于一个3格宽的单行网格，有两类排列方式：不含相同色的相邻列的排列（三个颜色各不相同）和两个颜色相同、一个颜色不同的排列。对于第一种情况，有6种排列（如红黄绿、红绿黄等），对于第二种情况，也有6种（如红红黄、黄红红等）。当增加更多行时，下一行的颜色排列方式会依赖于上一行的颜色排列。具体地说，对于第一种类型的排列，下一行可以是第一种类型的3种排列或第二种类型的2种排列。对于第二种类型的排列，下一行可以是第一种类型的2种排列或第二种类型的2种排列。使用两个变量`a`和`b`分别跟踪第一种和第二种类型的排列数量，并迭代更新这些值直到达到所需的行数。最后，返回`a`和`b`的总和，即总的排列数量。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numOfWays(self, n: int) -> int:
a, b = 6, 6 # 初始化单行网格的两种排列数量
for _ in range(n-1): # 对于每一个额外的行，计算新的排列数
a, b = (3*a + 2*b) % 1000000007, (2*a + 2*b) % 1000000007 # 更新a与b的值，其中模运算确保结果不会溢出
return (a + b) % 1000000007 # 返回总排列数，再次模运算是为了确保结果正确
在这个题解中，a和b分别代表两种不同的排列类型的数量。a代表行中三个颜色互不相同的排列数量，由于有三种颜色，可以任意排列，因此有3! = 6种可能（如红黄绿、红绿黄等）。b代表其中两个颜色相同，另一个颜色不同的排列数量，同样有6种（如红红黄、黄红红等）。初始化这两个值为6是因为在单行网格中，每种类型的排列都正好有6种可能性。
这些更新公式的系数来自于从一行的排列如何影响到下一行的可能排列。对于类型a（三个颜色各不相同的排列），在下一行可以有3种方式继续保持三个颜色各不相同，同时有2种方式转变为两个颜色相同的排列（类型b）。因此，新的a是旧的a乘以3加上旧的b乘以2。对于类型b（两个颜色相同的排列），它可以转变为类型a的排列有2种方式，也可以保持为类型b的排列有2种方式。因此新的b是旧的a乘以2加上旧的b乘以2。这些系数反映了每种排列转换的可能性。
两种排列类型分别是：类型a，其中每个格子的颜色完全不同，例如红黄绿。这种排列允许最大的变化性，因为每一列的颜色都可以在下一行中改变而不违反颜色不同的规则。类型b，其中两个格子颜色相同，第三个不同，例如红红黄。这种排列的变化性较小，因为保持相同的两个颜色在下一行中可能受到限制（例如，相同颜色的两列在下一行可能需要变化以避免与上一行相同的配置）。行与行之间的颜色分配受到前一行的排列类型的影响，每种类型都有特定的转换规则，这些规则定义了从一行到下一行的颜色变换方式。
模运算`(a + b) % 1000000007`用于确保结果在一个安全的整数范围内，防止溢出，并且满足可能的编程竞赛或工业应用中的数据规范要求，其中1000000007是一个大的素数。尽管在计算过程中已经对a和b进行了模运算，最后的结果a+b可能超过这个模数，因此在返回总数前再次进行模运算是必要的，以确保最终结果的正确性和一致性。