调试中...
中等
相关标签
相关企业
假如有一排房子，共 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 == ncosts[i].length == 31 <= n <= 1001 <= costs[i][j] <= 20
注意：本题与主站 256 题相同：https://leetcode-cn.com/problems/paint-house/
通过次数
56.9K
提交次数
73.8K
通过率
77.1%
相关企业
评论 (419)
💡 讨论区规则
1. 请不要在评论区发表题解！
2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。
3. 如果你需要整理题解思路，获得反馈从而进阶提升，可以去题解区进行。
来自 上海(编辑过)
2021.08.23
兄弟们，赚到了，原题是会员！
codclass Solution {
public:
int minCost(vector<vector<int>>& costs) {
int dp[203][3];
int n=costs.size();
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++){
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];
}
int ans=min(dp[n-1][0],dp[n-1][1]);
return min(ans,dp[n-1][2]);
}
};展开全部
79
展示 2 条回复
回复
来自 广东
2022.02.23
这不有个现成的dp数组^.^
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
for(int i = 1;i<costs.size();i++){
costs[i][0] += min(costs[i-1][1],costs[i-1][2]);
costs[i][1] += min(costs[i-1][0],costs[i-1][2]);
costs[i][2] += min(costs[i-1][0],costs[i-1][1]);
}
return min(costs[costs.size()-1][0],min(costs[costs.size()-1][1],costs[costs.size()-1][2]));
}
};展开全部
58
展示 2 条回复
回复
来自 河南
2024.09.08
动规，一个赞写一道题目
2
回复
来自 重庆
2022.06.25
假设我有一排房子，那我必不可能在这敲代码
18
展示 1 条回复
回复
来自 江苏
2024.08.15
class Solution {
public int minCost(int[][] costs) {
if(costs.length==1)
return compare(costs[0][0],costs[0][1],costs[0][2]);
int dp[][] = new int[costs.length][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for (int i = 1; i < costs.length; i++) {
dp[i][0] = Math.min(dp[i - 1][1] + costs[i][0], dp[i - 1][2] + costs[i][0]);
dp[i][1] = Math.min(dp[i - 1][0] + costs[i][1], dp[i - 1][2] + costs[i][1]);
dp[i][2] = Math.min(dp[i - 1][1] + costs[i][2], dp[i - 1][0] + costs[i][2]);
}
return compare(dp[costs.length - 1][0], dp[costs.length - 1][1], dp[costs.length - 1][2]);
}
public int compare(int a, int b, int c) {
int temp_max = Math.min(a, b);
return Math.min(temp_max, c);
}
}展开全部
1
回复
来自 美国
2024.08.14
通过率这么高？搁着cv是吧？
1
回复
来自 江苏
2022.06.25
看了评论区大佬们，我还要继续加油！！！
7
回复
来自 重庆
2024.02.29
动态规划，dp数组
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
//状态表示
//状态转移方程： dp[i][j] = costs[i][j]+min(dp[i-1][!j])
int n = costs.size();
vector<vector<int>> dp(n,vector<int>(3));
//初始化
for(int i = 0;i<3;++i)
{
dp[0][i] = costs[0][i];
}
for(int i = 1;i<n;++i)
{
dp[i][0] = costs[i][0]+min(dp[i-1][1],dp[i-1][2]);
dp[i][1] = costs[i][1]+min(dp[i-1][0],dp[i-1][2]);
dp[i][2] = costs[i][2]+min(dp[i-1][0],dp[i-1][1]);
}
return min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
}
};展开全部
1
回复
来自 北京
2022.06.30
时代在进步，打家劫舍的小偷转行刷油漆了
class Solution {
public int minCost(int[][] costs) {
int[][] costValue = new int[costs.length][3];
costValue[0][0] = costs[0][0];
costValue[0][1] = costs[0][1];
costValue[0][2] = costs[0][2];
for (int index = 1; index < costs.length; index++) {
costValue[index][0] = Math.min(costs[index][0] + costValue[index - 1][1], costs[index][0] + costValue[index - 1][2]);
costValue[index][1] = Math.min(costs[index][1] + costValue[index - 1][0], costs[index][1] + costValue[index - 1][2]);
costValue[index][2] = Math.min(costs[index][2] + costValue[index - 1][0], costs[index][2] + costValue[index - 1][1]);
}
return Math.min(Math.min(costValue[costs.length - 1][0], costValue[costs.length - 1][1]), costValue[costs.length - 1][2]);
}
}展开全部
3
回复
来自 上海
2021.10.27
CPP
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
//记录当前房子是红，蓝，绿色的花费
int size = costs.size();
int r = costs[0][0], b = costs[0][1], g = costs[0][2];
for(int i = 1; i < size; ++i){
int tr = r, tb = b, tg = g;
r = min(tg, tb) + costs[i][0];
b = min(tr, tg) + costs[i][1];
g = min(tr, tb) + costs[i][2];
}
return min(r, min(b, g));
}
};展开全部
3
展示 2 条回复
回复
贡献者
© 2025 领扣网络（上海）有限公司
3 人在线
行 1，列 1