Today’s problem

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

Intuition

In this question, we find that m is relatively small compared with n. As $m \le 5$, and $n \le 1000$. Then we may consider to enumerate all solutions for a column, then elaborate it to the whole matrix. When elaborating it to the whole matrix, we figure out a thing: whatever a column is painted, the only influence is its next column, while future columns will not influence previous columns. This makes DP possible.

Approach

Therefore, here is our approach:

  1. First, we need to find out how many valid patterns are there in a column. Therefore, we can perform a dfs to search for all possible combinations.
  2. Second, we need to know which two patterns can be in adjcent columns, so we enumerate through each pair of patterns, and then test whether they can be in adjcent rows or not.
  3. Third, we use DP to elaborate from one column to the next. In this case, the DP formular will be: $DP[col][case_x] = \sum DP[col-1][case_y]. \forall \text{casex and casey can be in two adjcent columns}$.
  4. Finally, all we need to do is to add up all the cases of the final column of DP to get our answer.

Complexity

  • Time complexity: $O(3^{2m} \times n)$

  • Space complexity: $O(3^{2m})$

Code

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