DP java
IntuitionDPApproachBitmask to store previous stateComplexity
Time complexity: 243 * O(n)

Space complexity: 243 * O(n)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
DP

# Approach
<!-- Describe your approach to solving the problem. -->
Bitmask to store previous state

# Complexity
- Time complexity: 243 * O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: 243 * O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    final int RED = 0;
    final int GREEN = 1;
    final int BLUE = 2;
    final int TOTAL_COLOR = 3;

    int maxColumn;
    int maxRow;

    int MOD = 1_000_000_007;

    Map<Integer, Map<Integer, Long>> memoi = new HashMap<>();

    /**
     * time complexity: (3 ^ m) * O(n)
     * @param m 1 <= m <= 5
     * @param n 1 <= n <= 1000
     */
    public int colorTheGrid(int m, int n) {
        maxRow = m;
        maxColumn = n;
        return (int) dp(-1, 0);
    }

    long dp(int previousColumnTotalValue, int columnIndex) {
        if (columnIndex == maxColumn) return 1;

        Long memoiValue = Optional.ofNullable(memoi.get(previousColumnTotalValue)).map(map -> map.get(columnIndex)).orElse(null);
        if (memoiValue != null) {
            return memoiValue;
        }

        List<Integer> availableColumns = new ArrayList<>();
        buildColumns(previousColumnTotalValue, 0, -1, 0, availableColumns);
        Long currentValue = availableColumns.stream()
            .map(columnTotalValue -> dp(columnTotalValue, columnIndex + 1) % MOD)
            .reduce(Long::sum)
            .map(value -> value % MOD)
            .orElse(0L);
        memoi.computeIfAbsent(previousColumnTotalValue, (key) -> new HashMap<>()).put(columnIndex, currentValue);
        return currentValue;
    }

    void buildColumns(int previousColumnTotalValue, int currentColumnValue, int previousRowColor, int rowIndex, List<Integer> columnsValues) {

        if (rowIndex == maxRow) {
            columnsValues.add(currentColumnValue);
            return;
        }

        for (int color = RED; color < TOTAL_COLOR; color++) {
            if (previousColumnTotalValue != -1) {
                int previousColumnColor = getColorAt(previousColumnTotalValue, rowIndex);
                if (color == previousColumnColor) continue;
            }
            if (rowIndex > 0 && color == previousRowColor) continue;
            int newColValue = pushColor(currentColumnValue, color, rowIndex);
            buildColumns(previousColumnTotalValue, newColValue, color, rowIndex + 1, columnsValues);
        }
    }

    /**
     *
     * @param color { red: 0, green: 1, blue: 2 }
     * @return new column value
     */
    public int pushColor(int currentColumnValue, int color, int rowIndex) {
        return currentColumnValue + color * (int) Math.pow(TOTAL_COLOR, rowIndex);
    }

    public int getColorAt(int columnValue, int rowIndex) {
        return (columnValue / ((int) Math.pow(TOTAL_COLOR, rowIndex))) % TOTAL_COLOR;
    }
}
```
['Java']