剑指OfferII 91. 粉刷房子

剑指OfferII 91. 粉刷房子

题目描述

假如有一排房子，共 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 提示: costs.length == n costs[i].length == 3 1 <= n <= 100 1 <= costs[i][j] <= 20

题目解析

解题思路

本题是典型的动态规划问题，要求相邻房子颜色不同，求最小总花费。参考代码使用二维 DP 数组 dp[i][j] 表示粉刷前 i 个房子（0-indexed）、且第 i 个房子刷颜色 j 时的最小总花费。由于相邻颜色不能相同，第 i 个房子刷颜色 j 时，第 i-1 个房子只能刷另外两种颜色，因此状态转移方程为：

dp[i][j] = min(dp[i-1][k]) + costs[i][j]   (k ≠ j)

最终答案为 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])。

关键步骤

1. 初始化 dp 数组：大小为 n×3，全部置 0。 2. base case：第 0 个房子的花费就是 costs[0] 本身，直接赋值：

   dp[0][0] = costs[0][0]
   dp[0][1] = costs[0][1]
   dp[0][2] = costs[0][2]

3. 状态转移：从 i=1 到 n-1 遍历每个房子，对每种颜色 j，取前一个房子另外两种颜色的 dp 值的最小值，加上当前房子刷颜色 j 的花费：

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

4. 返回结果：取 dp[n-1] 中的最小值。

示意图（以 n=3 为例）：

房子0: [17, 2, 17]   → dp[0] = [17, 2, 17]
房子1: [16,16, 5]    → dp[1][0] = min(2,17)+16 = 18
                      dp[1][1] = min(17,17)+16 = 33
                      dp[1][2] = min(17,2)+5  = 7
房子2: [14, 3, 19]   → dp[2][0] = min(33,7)+14 = 21
                      dp[2][1] = min(18,7)+3  = 10
                      dp[2][2] = min(18,33)+19= 37
最终 min(21,10,37) = 10

复杂度分析

• 时间复杂度：O(n)，只需遍历一次所有房子，每个房子进行常数次比较和加法。
• 空间复杂度：O(n×3) = O(n)，使用了一个 n×3 的二维数组。若采用滚动数组优化可降至 O(1)，但参考代码未做此优化。