粉刷房子如何用动态规划求最小成本？为什么相邻房子颜色不能相同？

简化版

粉刷房子用 dp[i][c] 表示刷到第 i 个房子且第 i 个房子颜色为 c 时的最小成本。因为相邻房子颜色不能相同，所以当前颜色 c 只能从上一间的其他颜色转移过来。

详细版

如果只有 3 种颜色，转移很直接：dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])，其他颜色同理。初始化为第一间房子的各颜色成本。最终答案是最后一行三个状态的最小值。

时间复杂度 O(n*3)，空间可以从二维数组压缩到 3 个变量。如果颜色数扩展到 k，朴素转移是 O(nk²)，可以维护上一行最小值和次小值优化到 O(nk)。

完整版教学

一、为什么每个房子只记录一种颜色状态

题目限制相邻房子不能同色，所以第 i 间房子的选择只和第 i-1 间房子的颜色有关。更早的房子影响已经被上一状态的最小成本吸收了。

房子 0   房子 1   房子 2
红/蓝/绿 红/蓝/绿 红/蓝/绿

只要知道“上一间刷成某颜色时的最低成本”，当前就可以避开同色并加上当前成本。

二、状态定义和转移公式

定义：

dp[i][c] = 第 i 间房子刷成颜色 c，且前 i 间都合法的最小总成本

如果颜色是红、蓝、绿，编号为 0、1、2：

dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

当前颜色	可来自上一间颜色
红	蓝、绿
蓝	红、绿
绿	红、蓝

转移里的 min 表示在满足约束的前提下选成本最低的前缀。

三、用数字例子推演

假设成本矩阵：

房子0: 红17 蓝2  绿17
房子1: 红16 蓝16 绿5
房子2: 红14 蓝3  绿19

第一行：

dp[0] = [17, 2, 17]

第二行：

红 = 16 + min(2,17) = 18
蓝 = 16 + min(17,17) = 33
绿 = 5  + min(17,2) = 7

继续计算最后一行，答案会是 10，对应蓝、绿、蓝。

记忆钩子：状态机 DP 常见套路是“当前状态固定，上一状态只能从合法集合里选”。

四、代码模板

int minCost(int[][] costs) {
    int n = costs.length;
    int[][] dp = new int[n][3];
    for (int c = 0; c < 3; c++) dp[0][c] = costs[0][c];
    for (int i = 1; i < n; i++) {
        dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = costs[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
    }
    return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
}

最终不是固定最后一种颜色，而是在最后一间房子的所有颜色里取最小值。

五、空间优化怎么做

因为第 i 行只依赖第 i-1 行，可以只保留上一行三个值：

int r = costs[0][0], b = costs[0][1], g = costs[0][2];
for (int i = 1; i < costs.length; i++) {
    int nr = costs[i][0] + Math.min(b, g);
    int nb = costs[i][1] + Math.min(r, g);
    int ng = costs[i][2] + Math.min(r, b);
    r = nr; b = nb; g = ng;
}

必须用临时变量 nr, nb, ng，不能边算边覆盖，否则后面的颜色会读到本轮新值。

六、扩展到 k 种颜色怎么办

如果有 k 种颜色，朴素写法是对每个当前颜色枚举上一行所有不同颜色，复杂度 O(nk²)。优化方法是维护上一行的最小值和次小值。

如果当前颜色不是上一行最小值的颜色，用最小值
如果当前颜色正好等于上一行最小值颜色，用次小值

情况	可用前缀成本
当前颜色 != minColor	prevMin
当前颜色 == minColor	prevSecondMin

这样每一行只需要 O(k)。

七、常见误区与追问

误区：每间房都选当前成本最低颜色。 可能和相邻房子颜色冲突，不能局部贪心。
误区：更新滚动变量时直接覆盖。 会让同一行状态互相污染。
误区：最终返回最后一种颜色的成本。 最后一间可以是任意颜色，要取最小。
追问：为什么只依赖上一间？ 约束只发生在相邻房子之间，历史成本已经压缩进上一状态。
追问：k 种颜色怎么优化？ 维护上一行最小值和次小值，避免每次枚举所有颜色。
追问：这算状态机 DP 吗？ 可以看成颜色状态之间按合法转移边移动。

八、加强记忆

粉刷房子的核心是“当前颜色固定，上一间不能同色”。dp[i][c] 让当前选择具体化，然后只从上一行其他颜色里取最小。三色版公式很短，滚动优化要用临时变量；k 色版记住最小值和次小值这对组合，面试追问就能接住。

简化版

详细版