[LeetCode] 256. Paint House

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on…

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

Constraints:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

粉刷房子。

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/JEj789
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题是典型的动态规划/背包问题。因为每个房子涂什么颜色是取决于他的两个邻居的，但是因为我们不能从两边往中间扫描，所以我们可以把这个条件转化为每个房子涂什么颜色是跟他的左邻居有关的。为了得到最小的成本，我们只能试着去找所有可能的组合，然后在最后的结果里找那个成本最小的。所以我们需要一个二维 dp 数组来记录中间过程。dp 的第一维是表示第 i 个房子，第二维 j 是表示涂什么颜色，可以用0,1,2分别表示三种不同的颜色。dp 数组的定义是对第 i 座房子涂 j 颜色的成本是多少。

dp的初始化就是对于第 0 个房子，我们分别对第一座房子涂不同的颜色。从第二座房子开始，如果当前这个房子是最后一个房子，那么到此为止的成本 = 前 i – 1 座房子的成本 + 当前房子涂一个不同于第 i – 1 座房子颜色的成本。具体参见代码。

时间O(n)

空间O(n^2)

Java实现

 1 class Solution {
 2     public int minCost(int[][] costs) {
 3         int len = costs.length;
 4         int[][] dp = new int[len][3];
 5         // 0, 1, 2表示三种不同颜色
 6         dp[0][0] = costs[0][0];
 7         dp[0][1] = costs[0][1];
 8         dp[0][2] = costs[0][2];
 9         for (int i = 1; i < len; i++) {
10             // 如果当前房子涂红色（0），那么成本就是前 i - 1 座房子的成本 + 前一座房子涂两个别的颜色之一的较小值
11             dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
12             dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
13             dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
14         }
15         return Math.min(dp[len - 1][0], Math.min(dp[len - 1][1], dp[len - 1][2]));
16     }
17 }

LeetCode 题目总结