这道题是状态压缩动态规划的经典应用，由于 m <= 5 很小，可以枚举所有合法的列状态进行转移。

解题思路

1. 状态定义

· 每一列用三进制表示（0、1、2 代表三种颜色），列内相邻行颜色不能相同
· dp[col][state]：前 col 列，最后一列状态为 state 的涂色方案数

2. 合法状态筛选

· 枚举所有 3^m 种可能的列状态
· 筛选出列内合法的状态：同一列相邻行颜色不同
· 对 m=5，最多 3^5 = 243 种状态，筛选后合法状态很少（m=5 时仅 48 个）

3. 状态转移

· 对于每两个相邻列，判断是否列间合法：相邻列的同一行颜色不同
· dp[col][cur] = sum(dp[col-1][prev])，其中 prev 和 cur 列间合法

4. 优化

· 预处理所有列间合法的状态对 (prev, cur)
· 使用滚动数组或一维 DP 优化空间

Java 代码

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int colorTheGrid(int m, int n) {
        // 1. 枚举所有可能的列状态（三进制）
        int totalStates = (int) Math.pow(3, m);
        List<Integer> validStates = new ArrayList<>();
        
        // 筛选列内合法的状态
        for (int state = 0; state < totalStates; state++) {
            if (isValidColumn(state, m)) {
                validStates.add(state);
            }
        }
        
        int size = validStates.size();
        
        // 2. 预处理状态转移关系
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            next.add(new ArrayList<>());
            for (int j = 0; j < size; j++) {
                if (isValidAdjacent(validStates.get(i), validStates.get(j), m)) {
                    next.get(i).add(j);
                }
            }
        }
        
        // 3. DP 初始化（第一列）
        int[] dp = new int[size];
        Arrays.fill(dp, 1);  // 第一列所有合法状态都有 1 种方案
        
        // 4. DP 递推
        for (int col = 1; col < n; col++) {
            int[] newDp = new int[size];
            for (int cur = 0; cur < size; cur++) {
                for (int prev : next.get(cur)) {
                    newDp[cur] = (newDp[cur] + dp[prev]) % MOD;
                }
            }
            dp = newDp;
        }
        
        // 5. 求和
        int result = 0;
        for (int val : dp) {
            result = (result + val) % MOD;
        }
        return result;
    }
    
    // 检查列内是否合法：相邻行颜色不同
    private boolean isValidColumn(int state, int m) {
        int prev = -1;
        for (int i = 0; i < m; i++) {
            int color = state % 3;
            if (color == prev) return false;
            prev = color;
            state /= 3;
        }
        return true;
    }
    
    // 检查两列之间是否合法：同一行颜色不同
    private boolean isValidAdjacent(int state1, int state2, int m) {
        for (int i = 0; i < m; i++) {
            if (state1 % 3 == state2 % 3) return false;
            state1 /= 3;
            state2 /= 3;
        }
        return true;
    }
}
```

复杂度分析

· 时间复杂度：O(n * K²)，其中 K 是合法状态数（m=5 时 K=48）
· 空间复杂度：O(K²) 用于存储转移关系，DP 数组 O(K)

关键点

1. 三进制表示：用 0、1、2 分别代表三种颜色，列状态用三进制整数表示
2. 两层合法性检查：
   · 列内：isValidColumn 检查相邻行颜色是否相同
   · 列间：isValidAdjacent 检查同一行颜色是否相同
3. 预处理优化：提前计算好状态转移关系，避免在 DP 循环中重复判断