力扣 LCR 091. 粉刷房子 —— 动态规划入门详解
引言
动态规划是算法面试中的"拦路虎"，许多初学者不知从何下手。今天讲解的「力扣 91. 粉刷房子」正是 DP 入门的绝佳练习题。它不像背包问题需要纠结"容量"维度，而是用最朴素的二维 DP 表格，清晰展示了状态定义、初始化、转移和返回的完整流程。无论你是算法新手还是面试备战者，这篇文章都会带你一步步拆解题目，让你真正理解 DP 的核心思想。让我们从一道题开始，打通动态规划的"任督二脉"
摘要
本文详细解析力扣 91「粉刷房子」的 DP 解法。给定n×3成本矩阵，求相邻颜色不同时的最小总花费。定义dp[i][j]为第i个房子刷颜色j的最小花费，转移方程dp[i][j]=costs[i][j]+min(dp[i-1][k]) (k≠j)。通过示例手动推导 DP 表格，并提供二维数组和 O(1) 滚动数组两种代码实现。重点总结三个易错点：维度理解、返回值、三数取最小值。时间 O(n)，空间可优化至 O(1)
目录
一、题目描述
二、动态规划思路
1. 为什么用 DP？
2. DP 数组的定义
3. DP 数组的构造（以示例为例）
4. 状态转移方程
三、Java 代码实现
四、代码优化（空间压缩）
五、易错点总结（特别重要）
⚠️ 注意点 1：DP 数组的构造维度
⚠️ 注意点 2：返回值不是 dp[n-1][2]
⚠️ 注意点 3：三个数取最小值的写法
六、复杂度分析
总结
一、题目描述
假如有一排房子，共n个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵costs来表示的。
例如，costs[0][0]表示第 0 号房子粉刷成红色的成本花费；costs[1][2]表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
示例 1：
输入: costs = [[17,2,17],[16,16,5],[14,3,19]] 输出: 10 解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。 最少花费: 2 + 5 + 3 = 10。示例 2：
输入: costs = [[7,6,2]] 输出: 2二、动态规划思路
1. 为什么用 DP？
这道题满足最优子结构：
第i个房子刷某种颜色的最小花费，只依赖于第i-1个房子刷其他两种颜色的最小花费。
因此我们可以用动态规划，从前往后依次推导。
2. DP 数组的定义
我们定义一个二维数组dp：
dp[i][j]：表示粉刷完前 i 个房子（0 ~ i），且第 i 个房子刷成颜色 j 时的最小总花费。其中：
i表示房子编号，范围0 ~ n-1j表示颜色，0=红色，1=蓝色，2=绿色
3. DP 数组的构造（以示例为例）
输入：
costs = [[17,2,17], [16,16,5], [14,3,19]]我们手动构造出dp数组：
| 房子 \ 颜色 | 红色 | 蓝色 | 绿色 |
|---|---|---|---|
| 0号房子 | 17 | 2 | 17 |
| 1号房子 | 18 | 33 | 7 |
| 2号房子 | 21 | 10 | 37 |
推导过程：
初始化第一行：
第 0 号房子刷任意颜色，花费就是它本身的成本。
→dp[0] = [17, 2, 17]第二行（1号房子）：
刷红色：
16 + min(dp[0][1], dp[0][2]) = 16 + min(2,17) = 18刷蓝色：
16 + min(dp[0][0], dp[0][2]) = 16 + min(17,17) = 33刷绿色：
5 + min(dp[0][0], dp[0][1]) = 5 + min(17,2) = 7
第三行（2号房子）：
刷红色：
14 + min(dp[1][1], dp[1][2]) = 14 + min(33,7) = 21刷蓝色：
3 + min(dp[1][0], dp[1][2]) = 3 + min(18,7) = 10刷绿色：
19 + min(dp[1][0], dp[1][1]) = 19 + min(18,33) = 37
最终，最后一个房子（2号房子）的最小花费是：
min(21, 10, 37) = 104. 状态转移方程
dp[i][j] = costs[i][j] + min(dp[i-1][k]) 其中 k ≠ j也就是说：当前房子刷颜色j的总花费 = 当前房子刷颜色j的成本 + 上一个房子刷另外两种颜色的较小值。
三、Java 代码实现
public class Main { public static void main(String[] args) { int[][] costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}}; System.out.println(minCost(costs)); // 输出 10 } public static int minCost(int[][] costs) { int M = costs.length; // 房子数量 int N = 3; // 颜色数量（红、蓝、绿） // dp[i][j]：前 i 个房子，第 i 个房子刷颜色 j 的最小总花费 int[][] dp = new int[M][N]; // 1. 初始化第一行 for (int j = 0; j < N; j++) { dp[0][j] = costs[0][j]; } // 2. 从第二个房子开始递推 for (int i = 1; i < M; i++) { for (int j = 0; j < N; j++) { int prevMin; if (j == 0) { // 当前刷红色，上一个只能是蓝色或绿色 prevMin = Math.min(dp[i-1][1], dp[i-1][2]); } else if (j == 1) { // 当前刷蓝色，上一个只能是红色或绿色 prevMin = Math.min(dp[i-1][0], dp[i-1][2]); } else { // 当前刷绿色，上一个只能是红色或蓝色 prevMin = Math.min(dp[i-1][0], dp[i-1][1]); } dp[i][j] = costs[i][j] + prevMin; } } // 3. 返回最后一个房子的最小花费 return Math.min(dp[M-1][0], Math.min(dp[M-1][1], dp[M-1][2])); } }运行结果：
四、代码优化（空间压缩）
因为dp[i]只依赖于dp[i-1]，我们可以用一维数组滚动更新，降低空间复杂度到O(1)：
public static int minCost(int[][] costs) { int n = costs.length; int[] dp = new int[3]; // 初始化第一行 dp[0] = costs[0][0]; dp[1] = costs[0][1]; dp[2] = costs[0][2]; for (int i = 1; i < n; i++) { int prev0 = dp[0], prev1 = dp[1], prev2 = dp[2]; dp[0] = costs[i][0] + Math.min(prev1, prev2); dp[1] = costs[i][1] + Math.min(prev0, prev2); dp[2] = costs[i][2] + Math.min(prev0, prev1); } return Math.min(dp[0], Math.min(dp[1], dp[2])); }五、易错点总结（特别重要）
⚠️ 注意点 1：DP 数组的构造维度
本题虽然只有一个“房子数量”维度，但因为每个状态有 3 种颜色选择，所以用二维数组dp[n][3]来记录。
不要误以为需要“物品 + 容量”两个维度，那是 01 背包的思路，这里没有容量限制。
⚠️ 注意点 2：返回值不是dp[n-1][2]
很多同学想当然地认为最后一个元素就是答案，但这是错误的！
最后一个房子有三种可能颜色，应该取三种颜色中的最小值：
return Math.min(dp[M-1][0], Math.min(dp[M-1][1], dp[M-1][2]));
⚠️ 注意点 3：三个数取最小值的写法
Java 中Math.min()只支持两个参数，取三个数最小值要嵌套：
Math.min(a, Math.min(b, c))
六、复杂度分析
时间复杂度：
O(n * 3) = O(n)，只需要遍历每个房子一次空间复杂度：
二维数组版：
O(n * 3) = O(n)一维滚动数组版：
O(1)
总结
这道题是动态规划入门的经典题目，核心思想是：
定义
dp[i][j]表示第i个房子刷颜色j时的最小花费状态转移只依赖于前一个房子的两种颜色
最后取最后一个房子的三种颜色中的最小值
掌握了这道题，后续遇到“打家劫舍”、“股票买卖”等经典 DP 问题，思路也会更加清晰。
希望这篇文章能帮助你更好地理解动态规划！如果有问题，欢迎留言讨论 🚀
