这道题是一个三维动态规划问题，比标准的"粉刷房子"复杂很多，因为引入了**街区（neighborhood）**的概念。

题目理解

  • houses[i]：第 i 个房子的颜色（0 表示未粉刷，1…n 表示已粉刷）
  • cost[i][j]：将第 i 个房子粉刷成颜色 j+1 的花费
  • m：房子数量
  • n：颜色数量（1-based）
  • target：目标街区数量

街区定义：连续相同颜色的房子属于同一个街区。

例如：[1,1,2,2,2,1] 有 3 个街区：[1,1]、[2,2,2]、[1]

DP 状态定义

定义 dp[i][j][k] = 粉刷完前 i 个房子，第 i 个房子颜色为 j，形成 k 个街区的最小花费

  • i：0…m
  • j：1…n（颜色）
  • k：1…target

状态转移方程

对于第 i 个房子（1-based），尝试所有可能的颜色 j：

if (houses[i-1] != 0 && houses[i-1] != j) {
    // 第 i 个房子已固定颜色且不等于 j，跳过
    continue;
}

int paintCost = (houses[i-1] == j) ? 0 : cost[i-1][j-1];

然后考虑第 i-1 个房子的颜色 j0：

if (j0 == j) {
    // 颜色相同，街区数不变
    dp[i][j][k] = min(dp[i][j][k], dp[i-1][j0][k] + paintCost);
} else {
    // 颜色不同，街区数+1
    if (k > 1) {
        dp[i][j][k] = min(dp[i][j][k], dp[i-1][j0][k-1] + paintCost);
    }
}

完整代码 AC

class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        // dp[i][j][k]: 前i个房子，第i个颜色j，形成k个街区的最小花费
        int[][][] dp = new int[m + 1][n + 1][target + 1];
        int INF = (int)1e9;
        
        // 初始化
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(dp[i][j], INF);
            }
        }
        
        // 第0个房子，颜色0，0个街区，花费0
        dp[0][0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            // 当前房子可选的颜色
            int startColor = 1, endColor = n;
            if (houses[i-1] != 0) {
                // 房子已上色，只能选这个颜色
                startColor = houses[i-1];
                endColor = houses[i-1];
            }
            
            for (int j = startColor; j <= endColor; j++) {
                int paintCost = (houses[i-1] == j) ? 0 : cost[i-1][j-1];
                
                for (int k = 1; k <= target; k++) {
                    // 枚举前一个房子的颜色
                    for (int j0 = 0; j0 <= n; j0++) {
                        if (dp[i-1][j0][k-1] == INF && dp[i-1][j0][k] == INF) {
                            continue;
                        }
                        
                        if (j0 == j) {
                            // 颜色相同，街区数不变
                            dp[i][j][k] = Math.min(dp[i][j][k], 
                                dp[i-1][j0][k] + paintCost);
                        } else {
                            // 颜色不同，街区数+1
                            if (k > 0) {
                                dp[i][j][k] = Math.min(dp[i][j][k], 
                                    dp[i-1][j0][k-1] + paintCost);
                            }
                        }
                    }
                }
            }
        }
        
        // 取结果：前m个房子，颜色任意，恰好target个街区
        int ans = INF;
        for (int j = 1; j <= n; j++) {
            ans = Math.min(ans, dp[m][j][target]);
        }
        return ans == INF ? -1 : ans;
    }
}

时间复杂度优化

上面的代码是 O(m * n² * target)，可以优化到 O(m * n * target)：

核心优化：当计算 dp[i][j][k] 时，不需要遍历所有 j0，可以维护两个变量：

  • bestSame = 当前颜色 j 在上一轮的最优值
  • bestDiff = 上一轮所有颜色的最优值
class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int INF = (int)1e9;
        int[][][] dp = new int[m + 1][n + 1][target + 1];
        
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(dp[i][j], INF);
            }
        }
        
        dp[0][0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 跳过不可用的颜色
                if (houses[i-1] != 0 && houses[i-1] != j) {
                    continue;
                }
                
                int paintCost = (houses[i-1] == j) ? 0 : cost[i-1][j-1];
                
                // 求上一轮的最小值和第二小值，用于 O(1) 转移
                int min1 = INF, min2 = INF;
                int colorOfMin1 = -1;
                
                for (int j0 = 1; j0 <= n; j0++) {
                    if (dp[i-1][j0][target - 1] < min1) {
                        min2 = min1;
                        min1 = dp[i-1][j0][target - 1];
                        colorOfMin1 = j0;
                    } else if (dp[i-1][j0][target - 1] < min2) {
                        min2 = dp[i-1][j0][target - 1];
                    }
                }
                
                for (int k = 1; k <= target; k++) {
                    // 颜色相同的情况
                    dp[i][j][k] = Math.min(dp[i][j][k], 
                        dp[i-1][j][k] + paintCost);
                    
                    // 颜色不同的情况：使用上一轮的最优值
                    if (k > 1) {
                        if (colorOfMin1 != j) {
                            dp[i][j][k] = Math.min(dp[i][j][k], 
                                min1 + paintCost);
                        } else {
                            dp[i][j][k] = Math.min(dp[i][j][k], 
                                min2 + paintCost);
                        }
                    }
                }
            }
        }
        
        int ans = INF;
        for (int j = 1; j <= n; j++) {
            ans = Math.min(ans, dp[m][j][target]);
        }
        return ans == INF ? -1 : ans;
    }
}

空间优化

由于 dp[i] 只依赖 dp[i-1]，可以优化到二维：

class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int INF = (int)1e9;
        int[][] dp = new int[n + 1][target + 1];
        int[][] prev = new int[n + 1][target + 1];
        
        for (int j = 0; j <= n; j++) {
            Arrays.fill(dp[j], INF);
            Arrays.fill(prev[j], INF);
        }
        prev[0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(dp[j], INF);
            }
            
            for (int j = 1; j <= n; j++) {
                if (houses[i-1] != 0 && houses[i-1] != j) {
                    continue;
                }
                
                int paintCost = (houses[i-1] == j) ? 0 : cost[i-1][j-1];
                
                for (int k = 1; k <= target; k++) {
                    // 颜色相同
                    dp[j][k] = Math.min(dp[j][k], prev[j][k] + paintCost);
                    
                    // 颜色不同
                    if (k > 1) {
                        for (int j0 = 1; j0 <= n; j0++) {
                            if (j0 != j) {
                                dp[j][k] = Math.min(dp[j][k], 
                                    prev[j0][k-1] + paintCost);
                            }
                        }
                    }
                }
            }
            
            // 交换 dp 和 prev
            int[][] temp = prev;
            prev = dp;
            dp = temp;
        }
        
        int ans = INF;
        for (int j = 1; j <= n; j++) {
            ans = Math.min(ans, prev[j][target]);
        }
        return ans == INF ? -1 : ans;
    }
}

关键点总结

  1. 状态定义：三维 DP，核心是 (位置, 颜色, 街区数)
  2. 已上色的房子：只能选择固定颜色，花费为 0
  3. 街区数变化规则：颜色相同则不变，不同则 +1
  4. 时间复杂度：O(m × n² × target) 可优化到 O(m × n × target)
  5. 边界条件：第 0 个房子用虚拟颜色 0，0 个街区，花费 0
# leetcode # 数据结构 # 动态规划 # 算法 # linux
Logo
DeepSeek技术社区

欢迎加入DeepSeek 技术社区。在这里，你可以找到志同道合的朋友，共同探索AI技术的奥秘。

更多推荐

cover

DeepSeek RAG 查询缓存命中率优化：如何从 30% 提升到 80% 的工程实践

avatar DeepSeek技术社区
cover

DeepSeek-V4 服务健康检查：为什么你的离线评测全绿，上线却崩了？

avatar DeepSeek技术社区
cover

DeepSeek输出护栏实战：如何用结构化JSON抵御越狱与幻觉

avatar DeepSeek技术社区