class Solution {
public:
int minCost(vector<vector<int>>& costs) {
}
};
256. 粉刷房子
假如有一排房子，共 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原站题解
javascript 解法, 执行用时: 48 ms, 内存消耗: 41.7 MB, 提交时间: 2023-10-21 19:43:47
/**
* @param {number[][]} costs
* @return {number}
*/
var minCost = function(costs) {
if(costs.length==0){
return 0;
}
let previousRow = costs[costs.length-1];
for(let n = costs.length-2;n>=0;n--){
let currentRow = costs[n];
// 把第 n 栋房子漆成红色的总成本。
currentRow[0] += Math.min(previousRow[1], previousRow[2]);
// 把第 n 栋房子漆成绿色的总成本。
currentRow[1] += Math.min(previousRow[0], previousRow[2]);
// 把第 n 栋房子漆成蓝色的总成本。
currentRow[2] += Math.min(previousRow[0], previousRow[1]);
previousRow = currentRow;
}
return Math.min(Math.min(previousRow[0],previousRow[1]),previousRow[2])
};
cpp 解法, 执行用时: 8 ms, 内存消耗: 9.9 MB, 提交时间: 2023-10-21 19:43:35
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if(costs.size()==0){
return 0;
}
auto previousRow = costs.back();
for(int n = costs.size()-2;n>=0;n--){
auto currentRow = costs[n];
// 把第 n 栋房子漆成红色的总成本。
currentRow[0] += min(previousRow[1], previousRow[2]);
// 把第 n 栋房子漆成绿色的总成本。
currentRow[1] += min(previousRow[0], previousRow[2]);
// 把第 n 栋房子漆成蓝色的总成本。
currentRow[2] += min(previousRow[0], previousRow[1]);
previousRow = currentRow;
}
return *min_element(previousRow.begin(),previousRow.end());
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.8 MB, 提交时间: 2023-10-21 19:43:23
func minCost(costs [][]int) int {
if len(costs)== 0{
return 0
}
previousRow:=costs[len(costs)-1]
for n:=len(costs)-2;n>=0;n--{
currentRow:=costs[n]
// 把第 n 栋房子漆成红色的总成本。
currentRow[0] += min(previousRow[1], previousRow[2]);
// 把第 n 栋房子漆成绿色的总成本。
currentRow[1] += min(previousRow[0], previousRow[2]);
// 把第 n 栋房子漆成蓝色的总成本。
currentRow[2] += min(previousRow[0], previousRow[1]);
previousRow = currentRow;
}
return min(previousRow[0],min(previousRow[1],previousRow[2]))
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-21 19:43:05
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
for n in reversed(range(len(costs) - 1)):
# 把第 n 栋房子漆成红色的总成本。
costs[n][0] += min(costs[n + 1][1], costs[n + 1][2])
# 把第 n 栋房子漆成绿色的总成本。
costs[n][1] += min(costs[n + 1][0], costs[n + 1][2])
# 把第 n 栋房子漆成蓝色的总成本。
costs[n][2] += min(costs[n + 1][0], costs[n + 1][1])
if len(costs) == 0: return 0
return min(costs[0]) # 返回第一行中的最小值。
def minCost2(self, costs: List[List[int]]) -> int:
import copy
if len(costs) == 0: return 0
previous_row = costs[-1]
for n in reversed(range(len(costs) - 1)):
current_row = copy.deepcopy(costs[n])
# 把第 n 栋房子漆成红色的总成本
current_row[0] += min(previous_row[1], previous_row[2])
# 把第 n 栋房子漆成绿色的总成本。
current_row[1] += min(previous_row[0], previous_row[2])
# 把第 n 栋房子漆成蓝色的总成本。
current_row[2] += min(previous_row[0], previous_row[1])
previous_row = current_row
return min(previous_row)
java 解法, 执行用时: 1 ms, 内存消耗: 41.9 MB, 提交时间: 2023-10-21 19:41:18
class Solution {
public int minCost(int[][] costs) {
int[][] dp = new int[costs.length][3];
int redCost = costs[0][0], blueCost = costs[0][1], greenCost = costs[0][2];
for (int i = 1; i < costs.length; i++) {
int newRedCost = Math.min(blueCost, greenCost) + costs[i][0];
int newBlueCost = Math.min(redCost, greenCost) + costs[i][1];
int newGreenCost = Math.min(redCost, blueCost) + costs[i][2];
redCost = newRedCost;
blueCost = newBlueCost;
greenCost = newGreenCost;
}
return Math.min(redCost, Math.min(blueCost, greenCost));
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 41.8 MB, 提交时间: 2023-10-21 19:41:06
class Solution {
public int minCost(int[][] costs) {
int[][] dp = new int[costs.length][3];
// 0 - 红色
// 1 - 蓝色
// 2 - 绿色
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], 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[costs.length-1][0], Math.min(dp[costs.length-1][1], dp[costs.length-1][2]));
}
}