[Python3] DP Rolling Array & Memo | 70% Time & 95% Space
\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        MOD = 10 ** 9 + 7\n        # Get valid states for a column\n        valid_states 
```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        MOD = 10 ** 9 + 7\n        # Get valid states for a column\n        valid_states = generate_states(m)\n        # Init rolling array dp\n        dp = [[0] * len(valid_states) for _ in range(2)]\n        # Init the first column of dp to all ones\n        for i in range(len(dp[0])):\n            dp[0][i] = 1\n\n        # Memorize valid current and previous states pairs\n        # memo: {(current state index, [previous valid state indexes])}\n        memo = {}\n        for i in range(1, n):\n            for j in range(len(valid_states)):\n                # Init the dp value of current column at this state to zero\n                dp[i % 2][j] = 0\n                # Iterate through all the valid states in previous column\n                # First check if the current state index is in memo\n                if j in memo:\n                    for k in memo[j]:\n                        dp[i % 2][j] = (dp[i % 2][j] + dp[(i - 1) % 2][k]) % MOD\n                    continue\n\n                # If not, iterate through all the valid states in previous column\n                valid_prev_states = []\n                for k in range(len(valid_states)):\n                    # Accumulate to the dp value of current column at this state if the two states are valid\n                    if check_valid_states(valid_states[j], valid_states[k]):\n                        dp[i % 2][j] = (dp[i % 2][j] + dp[(i - 1) % 2][k]) % MOD\n                        valid_prev_states.append(k)\n\n                # Save the current state index and previous valid state indexes list to memo\n                memo[j] = valid_prev_states\n        \n        # Add up the dp values of the last column\n        res = 0\n        for i in range(len(dp[0])):\n            res = (res + dp[(n - 1) % 2][i]) % MOD\n        return res\n\ndef generate_states(m):\n    states = []\n    # Iterate over all possible states in 10 digit base\n    for i in range(3 ** m):\n        state_tmp = i\n        state = []\n        # Convert the state to 3 digit base\n        for j in range(m):\n            last_bit = state_tmp % 3\n            if state and last_bit == state[-1]:\n                break\n            state.append(last_bit)\n            state_tmp //= 3\n\n        # Add the state to states if valid\n        if len(state) == m:\n            states.append(state)\n    \n    return states\n\ndef check_valid_states(state1, state2):\n    for i in range(len(state1)):\n        if state1[i] == state2[i]:\n            return False\n    return True\n```
['Dynamic Programming', 'Memoization']