力扣 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. 为什么用 DP2. DP 数组的定义3. DP 数组的构造以示例为例4. 状态转移方程三、Java 代码实现四、代码优化空间压缩五、易错点总结特别重要⚠️ 注意点 1DP 数组的构造维度⚠️ 注意点 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 数组的定义我们定义一个二维数组dpdp[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号房子172171号房子183372号房子211037推导过程初始化第一行第 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])); }五、易错点总结特别重要⚠️ 注意点 1DP 数组的构造维度本题虽然只有一个“房子数量”维度但因为每个状态有 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 问题思路也会更加清晰。希望这篇文章能帮助你更好地理解动态规划如果有问题欢迎留言讨论