别被“涂颜色”骗了——从「栅栏涂色（Paint Fence）」看动态规划真正的思维方式

别被“涂颜色”骗了

从「栅栏涂色（Paint Fence）」看动态规划真正的思维方式

作者：Echo_Wish

一、引子：

一道题，为什么能坑这么多人？

先说个很真实的现象。

Paint Fence（栅栏涂色），在 LeetCode 里不算难题，
但我见过：

• 初学 DP 的同学写不出来
• 工作好几年的工程师写错边界
• 面试时“感觉会”，一写就炸

问题就一句话：

有 n 个栅栏，用 k 种颜色涂
要求不能有超过两个相邻栅栏颜色相同
问：有多少种涂法？

听起来是不是很像“排列组合 + 一点限制”？

但这道题最坑的地方就在于：
你一旦用“组合思维”去硬算，基本必翻车。

二、先说结论：

这不是一道“数颜色”的题，而是一道“数状态”的题

很多人第一反应是：

“前一个栅栏几种情况，后一个再乘几种，不就完了？”

然后就开始写类似：<