1931. Painting a Grid With Three Different Colors

solution: 3 techniques used to solve this problem

1. Bit-mask to represent color combination of each column => each grid can be [0,1,2,3] => 2 bits => 2 * m (at most 1024) bits for entire column
1. DFS to calculate all possible masks of each column
1. DP to avoid duplicating calculation

time complexity:

each grid has 3 states=> each column has 3^m states => in total there are n * 3^m states
to calculate the result for a grid, we need call dfs(row+1, col, preColMask, setColor(curColMask, row, color), so the time complexity is T (k) = a * T (k-1) = ... = a ^ m where 1 <= a <= 2 (eg, if neighbors have same color, a = 2 else a = 1) so total time complexity is O(n * 3^m * 2^m)

space complexity:

memo needs O(n * 4^m)
space complexity for stack created for each column is O(4^m * 2^M) and there are at most n stacks total space complexity is O(n * 4^m * 2^m)

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:    
        def getColor(mask, row):
            return (mask >> (2 * row)) & 3
        
        def setColor(mask, row, color):
            return mask | (color << (2 * row))
        
        def dfs(row, col, preColMask, curColMask):
            if col == n:
                return 1
            if row == 0 and memo[col][preColMask]:
                return memo[col][preColMask]
            if row == m:
                return dfs(0, col+1, curColMask, 0)
            
            res = 0
            for color in [1, 2, 3]:
                if getColor(preColMask, row) != color and (row == 0 or getColor(curColMask, row-1) != color):
                    res = (res + dfs(row+1, col, preColMask, setColor(curColMask, row, color))) % MOD
                
            if row == 0:
                memo[col][preColMask] = res
            return res
        
        memo = [[0] * (4 ** m) for _ in range(n)]
        MOD = 10**9 + 7
        return dfs(0, 0, 0, 0)

1931. Painting a Grid With Three Different Colors - cocoder39/coco39_LC GitHub Wiki