今日题目

https://leetcode.com/problems/painting-a-grid-with-three-different-colors/

思路

本题中，我们发现 m 相对于 n 来说非常小。 由于 $m \le 5$，而 $n \le 1000$，因此可以考虑枚举单列的所有合法涂色方案，再将其推广到整个矩阵。 在推广过程中，我们发现一个关键性质：无论某列如何涂色，其影响只波及相邻的下一列，而不会影响更后面的列。这一特性使得 DP 成为可能。

方法

基于上述分析，我们的解题步骤如下：

  1. 首先，找出单列中所有合法的涂色模式。通过 DFS 搜索枚举所有可能的组合。
  2. 其次，判断哪两种模式可以出现在相邻的列中。枚举每对模式，检验它们是否满足相邻列的约束条件。
  3. 然后，利用 DP 从一列推导到下一列。DP 转移方程为：$DP[col][case_x] = \sum DP[col-1][case_y]，\forall \text{ case_x 与 case_y 可以出现在相邻两列中}$。
  4. 最后，将 DP 最后一列中所有情况的值累加，即为答案。

复杂度

  • 时间复杂度：$O(3^{2m} \times n)$

  • 空间复杂度：$O(3^{2m})$

代码

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        pat = []
        col = [0, 1, 2]
        def dfs(x, s):
            if x == m:
                pat.append(s)
                return
            for i in col:
                if x == 0 or s[x - 1] != i:
                    dfs(x + 1, s + [i])
        dfs(0, [])

        # till this step, we find all valid patterns for a column and store it in the pattern list.

        l = len(pat)
        valid = [[True for _ in range(l)] for _ in range(l)]

        for i in range(l):
            for j in range(i + 1, l):
                for k in range(m):
                    if pat[i][k] == pat[j][k]:
                        valid[i][j] = False
                        break
        
        # till this step, we find all the pattern pairs that is valid.

        dp = [[0 for _ in range(l)] for _ in range(n)]
        mod = 1_000_000_007
        for i in range(l):
            dp[0][i] = 1

        # for column 0, each pattern is valid.

        for i in range(1, n):
            for x in range(l):
                for y in range(x + 1, l):
                    if valid[x][y]:
                        dp[i][x] = (dp[i][x] + dp[i-1][y]) % mod
                        dp[i][y] = (dp[i][y] + dp[i-1][x]) % mod
        
        # we elaborate to the next column according to the DP formula.

        ans = 0
        for i in range(l):
            ans = (ans + dp[-1][i]) % mod

        # finally, we add up all the answers.

        return ans