剑指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

题目解析

题目在说什么

想象一下，你是一个粉刷匠，面前有一排房子，每个房子都要刷成红色、蓝色或绿色。但是有个规矩：相邻的两个房子不能刷成同一种颜色。每个房子刷不同颜色的价格不一样，比如第一个房子刷红色要17元，刷蓝色要2元，刷绿色要17元。你的任务是，给所有房子选颜色，既要遵守“相邻不同色”的规矩，又要让总花费最少。

题目给了你一个表格（就是那个 costs 数组），里面写着每个房子刷每种颜色的价格。比如 costs[0][0] 就是第0号房子刷红色的价格，costs[1][2] 是第1号房子刷绿色的价格。你需要算出最省钱的方案，并输出总花费。

思路是怎么来的

这个问题看起来有点复杂，因为每个房子的选择都会影响邻居。比如你给第0个房子选了蓝色，那第1个房子就不能选蓝色，只能从红色和绿色里挑。那第1个房子选了红色，第2个房子又不能选红色……这样一环扣一环。

新手可能会想：那我能不能先给第0个房子选最便宜的颜色，然后给第1个房子选除了那个颜色之外最便宜的，以此类推？但这样不一定对，因为“贪心”可能让你后面多花钱。比如例子中，第0个房子最便宜的是蓝色（2元），第1个房子不能选蓝色，最便宜的是绿色（5元），第2个房子不能选绿色，最便宜的是红色（14元），总花费是2+5+14=21元，但正确答案是10元，说明贪心会掉坑里。

那怎么办？我们可以换个思路：不要一次性决定所有房子，而是从第一个房子开始，慢慢往后推。每到一个新房子，我们只关心：如果这个房子刷某种颜色，那加上之前所有房子的最少花费是多少？因为相邻颜色不能相同，所以当前房子的颜色只受前一个房子的颜色影响，跟更前面的房子没关系（这就是“动态规划”的核心思想：当前状态只依赖上一个状态）。

具体来说，我们可以用一个表格（就是代码里的 dp 数组）来记录“到目前为止”的最优解。比如 dp[i][0] 表示：从第0个房子到第i个房子，并且第i个房子刷红色时，最少的总花费。这样，当我们计算第i个房子时，只需要看前一个房子（第i-1个）刷另外两种颜色时的最少花费，然后加上当前房子刷这个颜色的价格，取最小值就行了。

代码逐步拆解

我们来看参考代码，一步步解释它在干什么。

第一步：初始化 dp 数组

int n = costs.length;
int[][] dp = new int[n][3];

• n 是房子的数量，比如例子中有3个房子。
• dp 是一个二维数组，有n行（每个房子一行），每行有3列（对应红、蓝、绿三种颜色）。dp[i][j] 表示：从第0个房子到第i个房子，并且第i个房子刷颜色j时，最少的总花费。颜色j我们用0、1、2代表，比如0=红，1=蓝，2=绿。

第二步：设置 base case（起点）

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

• 对于第0个房子（第一个房子），它前面没有房子，所以没有“相邻颜色不同”的限制。因此，如果第0个房子刷红色，总花费就是它刷红色的价格（costs[0][0]），蓝色和绿色同理。这就是我们的起点。

第三步：填充 dp 数组（核心逻辑）

for (int i = 1; i < n; i++) {
    // 第 i 个房子刷第一个颜色（红色）
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];

    // 第 i 个房子刷第二个颜色（蓝色）
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];

    // 第 i 个房子刷第三个颜色（绿色）
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
}

• 从第1个房子（i=1）开始，一直到最后一个房子（i=n-1）。
• 对于每个房子，我们分别考虑它刷三种颜色的情况。
• 如果第i个房子刷红色（颜色0），那么前一个房子（第i-1个）就不能刷红色，只能刷蓝色（颜色1）或绿色（颜色2）。所以，我们要从 dp[i-1][1] 和 dp[i-1][2] 中选一个较小的，再加上当前房子刷红色的价格 costs[i][0]，就是“第i个房子刷红色”时的最少总花费。
• 蓝色和绿色同理：刷蓝色时，前一个房子不能刷蓝色，所以看红色和绿色；刷绿色时，前一个房子不能刷绿色，所以看红色和蓝色。