[LeetCode] Paint House 粉刷房子

简介:

There are a row of n houses, each house can be painted with one of the 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 a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

这道题说有n个房子,每个房子可以用红绿蓝三种颜色刷,每个房子的用每种颜色刷的花费都不同,限制条件是相邻的房子不能用相同的颜色来刷,现在让我们求刷完所有的房子的最低花费是多少。这题跟House Robber IIHouse Robber很类似,不过那题不是每个房子都抢,相邻的房子不抢,而这道题是每个房子都刷,相邻的房子不能刷同一种颜色。而Paint Fence那道题主要考察我们有多少种刷法,这几道题很类似,但都不一样,需要我们分别区分。但是它们的解题思想都一样,需要用动态规划Dynamic Programming来做,这道题我们需要维护一个二维的动态数组dp,其中dp[i][j]表示刷到第i+1房子用颜色j的最小花费,递推式为:

dp[i][j] = dp[i][j] + min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]);

这个也比较好理解,如果当前的房子要用红色刷,那么上一个房子只能用绿色或蓝色来刷,那么我们要求刷到当前房子,且当前房子用红色刷的最小花费就等于当前房子用红色刷的钱加上刷到上一个房子用绿色和刷到上一个房子用蓝色的较小值,这样当我们算到最后一个房子时,我们只要取出三个累计花费的最小值即可,参见代码如下:

解法一:

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty() || costs[0].empty()) return 0;
        vector<vector<int>> dp = costs;
        for (int i = 1; i < dp.size(); ++i) {
            for (int j = 0; j < 3; ++j) {
                dp[i][j] += min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]);
            }
        }
        return min(min(dp.back()[0], dp.back()[1]), dp.back()[2]);
    }
};

由于只有红绿蓝三张颜色,所以我们就可以分别写出各种情况,这样写可能比上面的写法更加一目了然一些,更容易理解一点吧:

解法二:

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty() || costs[0].empty()) return 0;
        vector<vector<int>> dp = costs;
        for (int i = 1; i < dp.size(); ++i) {
            dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] += min(dp[i - 1][0], dp[i - 1][1]);
        }
        return min(min(dp.back()[0], dp.back()[1]), dp.back()[2]);
    }
};

本文转自博客园Grandyang的博客,原文链接:粉刷房子[LeetCode] Paint House ,如需转载请自行联系原博主。

相关文章
|
安全
Leetcode 198. House Robber
一句话理解题意,有个偷马贼晚上要偷尽可能值钱的马,但连续两头马被偷会触发报警,问他如何在不触发报警(不偷连续的两匹马)的情况下偷到总价值最高马,返回最高总价值。
49 3
LeetCode 337. House Robber III
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
59 0
LeetCode 337. House Robber III
|
安全
LeetCode 213. House Robber II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
78 0
LeetCode 213. House Robber II
Leetcode:House Robber II
Leetcode:House Robber II
127 0
Leetcode:House Robber II
【LeetCode】House Robber III(337)
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automaticall
97 0
|
C++
LeetCode 198 House Robber(强盗盗窃最大值)(动态规划)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50560560 翻译 你是一个专业强盗,并计划沿街去盗窃每一个住户。
928 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
108 2