领导喝多了说：你们年轻人不要总想着钱，要想着怎么成长。我问：那为什么您每年都为了年终奖跟总部据理力争？结果领导让我去办公室聊聊

刷算法题的时候，最怕遇到那种乍一看“这题不难啊”，结果一写代码，调试半天才发现自己被“温柔陷阱”骗了的题目。比如这道「安装栅栏」（Fence Installation）——典型的动态规划题，我当时一眼看过去，心想：“这不就是个斐波那契吗？”结果写了两行代码就开始反思人生。

题目大意是这样的：你要给一个长度为 n 的院子安装栅栏，每个位置可以涂上 k 种颜色，但要求相邻的两个栅栏颜色不能相同。问一共有多少种不同的涂色方法？

这题跟一般的“排列组合”还不太一样，它看起来像是个组合问题，但本质上其实是个典型的动态规划场景，考察状态转移能力，关键是要想清楚“当前这个栅栏的颜色选择，受到前面多少个栅栏的影响”。

先别急，我们一步步来。

如果你上来就写个暴力递归，恭喜你，运行一次电脑升温两度。因为每个位置都有 k 种选择，要遍历所有组合的话复杂度是指数级的，面试官看你写这写法，心里已经把你发配到边疆了。

这题的核心思路其实是这样的：

我们用动态规划来做，定义两个状态：

• • same: 表示前两个栅栏颜色不同，但当前和前一个颜色相同的方案数
• • diff: 表示前两个栅栏颜色不同，且当前和前一个颜色也不同的方案数

状态转移公式就很优雅了：

same = prevDiff;
diff = (prevSame + prevDiff) * (k - 1);

别急，我来解释一下这个公式怎么来的。

• • 如果当前颜色和前一个一样（即 same），那前一个和再前一个就必须不同，所以只能从 prevDiff 状态转过来。
• • 如果当前颜色和前一个不同（即 diff），那前一个可以是 same 或 diff 状态过来的，而且当前颜色要从剩下的 k - 1 个颜色里选。

听着有点绕？直接上代码，直觉就来了：

publicintnumWays(int n, int k) {
if (n == 0) return0;
if (n == 1) return k;
if (n == 2) return k * k;

intsame= k;
intdiff= k * (k - 1);

for (inti=3; i <= n; i++) {
intprevSame= same;
intprevDiff= diff;

        same = prevDiff;
        diff = (prevSame + prevDiff) * (k - 1);
    }

return same + diff;
}

这个写法时间复杂度 O(n)，空间复杂度 O(1)，简直是内存和性能兼顾的模范代表。面试官看到你写出这个，一般会沉默两秒，然后说：“你这个人，我记住了”。

说到这，我想起之前一个朋友面试阿里，结果写了个暴力递归 + memo，虽然也能过，但运行速度感人。后来面试官说了句特别扎心的话：“你这个写法，我们拿去生产上跑一个亿条数据，服务器就烧了。”

所以说啊，有些题目并不是让你秀操作的，而是要你理解**“状态转移”**这个词的真正含义。很多同学一上来就“if else 写爆它”，但不去想“这个状态和前面是怎么关联的”，那和手搓排列组合没啥区别。

像这种看似简单，其实容易掉坑的题，还有不少，比如“打家劫舍”、“爬楼梯”之类的，其实都是换皮的状态转移问题，真正理解一次，后面全是变种题。

我觉得吧，刷题到一定阶段，就是理解模型、建立映射、秒出状态转移方程。到时候哪怕题目包装得再花哨，也逃不过你那双动态规划之眼👀。

说到底，算法不是让你死记硬背的，它是一种“套路思维”。写多了你就能明白，啥题都不怕，就怕思维不转弯。

好了，这题就到这吧，该理解的都讲了，代码也贴了。你要还不明白，那就多刷几遍，别怕，思维就是这样磨出来的。说不定哪天就靠这道“栅栏问题”冲进大厂，给自己的人生也涂个不一样的颜色。