自己工资15000，因为态度问题被领导边缘化，面了一家18000，结果提离职后，HR打电话说背调有点问题，暂缓入职。

写这类算法题，说实话，最怕的不是算法难，是产品一句“颜色不能相邻”就让你写一套能跑的，还得保证测试用例覆盖率100%，真是程序员的社死现场。

今天我们来聊一道在技术面试里经常能看到的算法题：用三种不同颜色为网格涂色，要求是相邻格子不能同色。表面是道算法题，其实背后暗藏着数据结构、递归、回溯优化的“套路”。说得再直白点，就是你能不能在“老板天天催进度”和“代码不能出Bug”的双重暴击下活下来。

我们先设定一下问题场景吧，不然容易发散。

假设我们有一个 m x n 的网格，每个格子可以涂成红、绿、蓝三种颜色中的一种（我们用数字 0，1，2 表示）。要求：相邻格子颜色不能一样，邻居指的是上下左右四个方向。我们要求的是有多少种合法的涂色方式。

说实话，我刚看到这题的时候，第一反应是：这不是图染色的经典问题吗？但是图染色一跑暴力就是死，尤其是加了“相邻不能相同”这个限制，就更像是写代码版的扫雷。

思路来了：

我们可以用 动态规划 + 状态压缩 来搞。也就是我们不一个格子一个格子地去尝试，而是以“行”为单位，把每一行的涂色状态压缩成一个整数来表示。

举个例子：
假设你有一个宽度为3的网格，一行有三个格子，那你可能有这么几种合法的涂色方式（因为相邻不能同色）：

• • 红绿蓝（012）
• • 绿蓝红（120）
• • 蓝红绿（201）
• • …等等

你发现没，其实这个一行的状态总共有  种。为啥？第一个格子你有3种选，第二个必须和前一个不一样，剩下2种，第三个也是2种。所以一行的状态组合我们可以先预处理出来。

来段Java代码演示一下预处理：

List<int[]> generateRowStates(int width) {
    List<int[]> res = newArrayList<>();
    dfs(newint[width], 0, res);
return res;
}

voiddfs(int[] row, int idx, List<int[]> res) {
if (idx == row.length) {
        res.add(row.clone());
return;
    }
for (intcolor=0; color < 3; color++) {
if (idx > 0 && row[idx - 1] == color) continue; // 相邻不能同色
        row[idx] = color;
        dfs(row, idx + 1, res);
    }
}

这个生成出来的 res 就是所有合法的一行状态。接下来干嘛？DP转移呗！

我们从上往下一行一行地涂，状态转移就靠“当前行”和“上一行”的配对关系：只要上下行之间不在同一个位置上用了同一个颜色，那这个组合就是合法的。

Map<String, Integer> dp = newHashMap<>();
for (int[] state : states) {
    dp.put(Arrays.toString(state), 1); // 第一行的状态初始化为1
}

for (inti=1; i < m; i++) {
    Map<String, Integer> newDp = newHashMap<>();
for (int[] prev : states) {
for (int[] curr : states) {
if (!isValid(prev, curr)) continue;
StringcurrKey= Arrays.toString(curr);
StringprevKey= Arrays.toString(prev);
            newDp.put(currKey, (newDp.getOrDefault(currKey, 0) + dp.get(prevKey)) % MOD);
        }
    }
    dp = newDp;
}

判断两个状态是否能上下拼接：

booleanisValid(int[] a, int[] b) {
for (inti=0; i < a.length; i++) {
if (a[i] == b[i]) returnfalse;
    }
returntrue;
}

最后我们把所有 dp 中的值加起来，就是最终的合法涂色方式数量。

讲真，这题虽然是算法题，但其实考的不是你代码写得多快，而是你能不能忍住“我用暴力也能跑”的冲动，冷静下来理一理状态、压缩一下空间，顺便把时间复杂度降到可接受的级别。

就像职场上经常遇到的事一样：你第一反应想撸起袖子上，但真正有效的是先停一停，看看是不是能用更优雅的方式解决问题。用脚踩油门很简单，知道什么时候踩刹车才难。

写这种题的时候，想想产品经理丢给你一个“这个按钮不能跟前面一个颜色一样”的需求，你的内心OS就该是：“又来了，又是个状态机”。

所以啊，写代码的快乐不是来自解决问题本身，而是来自你写完代码发现自己没踩坑、没爆栈、没TLE，还能通过所有测试样例时那一刻的成就感。

🧠💥 就这感觉，堪比通关游戏。

你问我有多难？我只能说：写完这题，我都能应聘你们UI团队了，毕竟我对颜色的搭配现在是真的很有心得了。