粉刷房子 Posted on 2022-06-25 00:00:00 2022-06-25 00:00:00 by Author 摘要 给你一排房子，对每一个房子涂不同的颜料，并且相邻的房子颜色不一样，颜料的价格也不一样，你能找到最优涂料选择，使得花费最小吗？ # 粉刷房子 1. 题目描述 - 假如有一排房子，共 `n` 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 - 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 - 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。 请计算出粉刷完所有房子最少的花费成本。 - **提示：** - `costs.length == n` - costs[i].length == 3 - `1 <= n <= 100` - 1 <= costs[i][j] <= 20` 2. 示例描述 - 示例一 ```java 输入：[[7,6,2]] 输出：2 ``` - 示例二 ```java 输入：[[17,2,17],[16,16,5],[14,3,19]] 输出：10.解释：将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。最少花费: 2 + 5 + 3 = 10 ``` 3. 解题思路 - 这道题目，是一道经典的动态规划问题，题目的链接为:[粉刷房子](https://leetcode.cn/problems/JEj789/)，首先对于动态规划问题，首先理清做题思路。一般动态规划题目的思路是：动态规划递推数组怎么定义，定义数组的含义是什么，如何初始化递推数组，递推方程是多少，遍历的方式是怎么样的。 - 这里我按照以上思路进行说明我自己的思路。首先定义动态递推数组，根据题目可知👉有`n`个房子，每个房子可以涂 三种颜料，那么自然而然可以想到数组定义为`dp[n][3]`，对于`dp[i][0]`表示在涂第i个房子时，如果用第一种颜料上色时，那么前i个房子所花费最小的费用为`dp[i][0]`,同理可得`dp[i][1]`,`dp[i][2]`的含义分别为涂第i个房子时，如果用第二种或者第三种颜料上色时，前i个房子所花费的最小的费用。 - 初始化数组：对于第一个房子初始化很简单，如果用第一种颜料上色那么所需要花费为:`dp[0][0]=cost[0][0]`,同理第二或者第三种颜料上色第一个房子情况是类似的。 - 递推方程: 对于涂第`i`个房子时用第一种颜料，那么第`i-1`个房子就不能涂第一种颜料，所以如果第`i`个房子涂第一种颜料时，那么，第`i-1`个房子颜色为第二种或者第三种，又因为是花费最小，所以选择`dp[i-1][1],dp[i-1][2]`最小的花费，在加上涂第`i`个房子的花费`cost[i][0]`，所以递推方程为:`dp[i][0]= Math.min(dp[i-1][1],dp[i-1][2])+cost[i][0]`,同理可得第`i`个房子涂第二和第三颜料时的递推方程类似。那么第`i`个房子分别用这三种颜料上色，我们找出用这三种颜料上色最小的花费，即表示涂完前`i`个房子，所需最小的花费就找到了。 - 遍历方式:从前往后遍历的 ，因为涂第`i`个房子时，依赖第`i-1`个房子涂料结果的进行选择，遍历完成后，dp数组的每一行表示在盖房子之前所有的房子用这三种颜料上完色后最小的花费。 - 最后需要得到结果是涂完所有房子所需的花费。那么就返回 dp数组最后一行中最小的值即可。 4. 代码示例， ```java public int minCost(int[][] costs) { //边界条件 if (costs.length == 0) return 0; //房子的个数 int n = costs.length; int[][] dp = new int[n][3]; //初始化过程 //第一个房子，粉刷消耗费用 dp[0][0] = costs[0][0]; //第二个房子，粉刷消耗费用 dp[0][1] = costs[0][1]; ////第三个房子，粉刷消耗费用 dp[0][2] = costs[0][2]; for (int i = 1; i < n; i++) { //对于第i个房子，如果涂第一种颜色，那么涂这种颜色时，前一个房屋就不能涂这种颜色的， //于是选择前i-1个花费最小的涂料选择加上涂该房屋所需要的花费，即是前i个房屋所需要的最小花费 //同理可得，涂第二，第三中颜料也是同样的思想。 dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]; dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]; dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]; } //最终返回最后一个房屋三种颜料花费最小的费用即可。 return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])); } ```
{{ item.content }}
{{ child.content }}