用三种不同颜色为网格涂色

难度: Hard

给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大，返回对 10⁹ + 7 取余的结果。

示例 1：

输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。

示例 2：

输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。

示例 3：

输入：m = 5, n = 5
输出：580986

提示：

1 <= m <= 5
1 <= n <= 1000

Submission

运行时间: 48 ms

内存: 16.6 MB

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        if m == 1:
            return 3 * pow(2, n - 1, (10 ** 9 + 7)) % (10 ** 9 + 7)
        if m == 2:
            return 6 * pow(3, n - 1, (10 ** 9 + 7)) % (10 ** 9 + 7)
        if m == 3:
            a = b = 6
            for i in range(n - 1):
                a, b = (a + b) << 1, (a << 1) + b * 3
            return (a + b) % (10 ** 9 + 7)
        if m == 4:
            a, b, c = 6, 12, 6
            for i in range(n - 1):
                a, b, c = (a << 1) + b + c, (a << 1) + (b << 2) + (c << 2), a + (b << 1) + c * 3
            return (a + b + c) % (10 ** 9 + 7)
        a, b, c, d, e, f = 6, 12, 6, 6, 12, 6
        for i in range(n - 1):
            a, b, c, d, e, f = (a << 1) + b + e, (a << 1) + b * 3 + (c << 1) + (d << 1) + (e << 1) + (f << 1), b + (c << 1) + (d << 1) + e + (f << 1), b + (c << 1) + d * 3 + (e << 1) + (f << 1), (a << 1) + (b << 1) + (c << 1) + (d << 2) + e * 3 + (f << 2), b + (c << 1) + (d << 1) + (e << 1) + (f << 1)
        return (a + b + c + d + e + f) % (10 ** 9 + 7)

Explain

该题解采用了动态规划的思路，对不同的行数 m 有不同的处理方式。对于 m = 1 和 m = 2，题解使用了数学公式直接计算。对于 m >= 3 的情况，题解通过构建状态转移方程来描述每一列可能的涂色方式与前一列的关系，并通过迭代计算出所有列的涂色方案总数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        MOD = 10**9 + 7
        if m == 1:
            # 对于 m = 1 的情况，有三种涂色方法，并且每列都可以选择两种颜色
            return 3 * pow(2, n - 1, MOD) % MOD
        if m == 2:
            # 对于 m = 2 的情况，首列有 6 种涂色方式，之后每列都有 3 种选择
            return 6 * pow(3, n - 1, MOD) % MOD
        if m == 3:
            a = b = 6
            # 使用两个变量 a 和 b 来追踪涂色方案的数量
            for i in range(n - 1):
                a, b = (a + b) << 1, (a << 1) + b * 3
            return (a + b) % MOD
        if m == 4:
            a, b, c = 6, 12, 6
            # 使用三个变量 a, b, c 来追踪涂色方案的数量
            for i in range(n - 1):
                a, b, c = (a << 1) + b + c, (a << 1) + (b << 2) + (c << 2), a + (b << 1) + c * 3
            return (a + b + c) % MOD
        a, b, c, d, e, f = 6, 12, 6, 6, 12, 6
        # 使用六个变量来追踪更复杂情况 (m = 5) 的涂色方案数量
        for i in range(n - 1):
            a, b, c, d, e, f = (a << 1) + b + e, (a << 1) + b * 3 + (c << 1) + (d << 1) + (e << 1) + (f << 1), b + (c << 1) + (d << 1) + e + (f << 1), b + (c << 1) + d * 3 + (e << 1) + (f << 1), (a << 1) + (b << 1) + (c << 1) + (d << 2) + e * 3 + (f << 2), b + (c << 1) + (d << 1) + (e << 1) + (f << 1)
        return (a + b + c + d + e + f) % MOD

Explore

对于 m = 1 的情况，网格退化为一个 1xN 的条形网格。第一列有3种颜色可供选择。从第二列开始，每一列的颜色都不能与前一列相同，因此每列都有2种选择（除去上一列的颜色）。这样，总的涂色方法数为 3 * 2^(N-1)。类似地，对于 m = 2 的情况，首列有 6 种不同的两色组合方式（考虑横向与纵向的颜色不同），之后每列根据前一列的颜色排列有3种不同的涂色方式，因此总的涂色方法数为 6 * 3^(N-1)。

在 m >= 3 的情况下，状态转移方程的构建依赖于前一列的涂色方式及其可能的变化。每个状态代表一种具体的列颜色组合，状态转移考虑了从前一列到当前列的所有有效涂色转换。例如，如果前一列的某种涂色方式为 'a'，那么当前列可能有多种符合色彩不相邻规则的涂色方式。通过定义每种涂色方式的可能转换，我们可以列出所有的转换关系，并使用动态规划数组来追踪每种状态到达当前列时的计数。迭代更新这些计数，直至最后一列，然后求和得到总的涂色方式。

在 m = 3 的情况下，网格为 3x1 的列状。变量 a 和 b 的初始值6来源于所有可能的开始涂色方式，它们都考虑了颜色在垂直方向上不相连的要求。具体来说，这6种涂色方式是通过列举所有颜色组合并排除任何具有相邻相同颜色的组合来得出的。例如，如果将颜色标记为1, 2, 3，则可能的涂色组合包括123, 132, 213, 231, 312, 321，其中没有相邻的颜色是相同的。