class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
}
};
265. 粉刷房子 II
假如有一排房子共有 n 幢，每个房子可以被粉刷成 k 种颜色中的一种。房子粉刷成不同颜色的花费成本也是不同的。你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
每个房子粉刷成不同颜色的花费以一个 n x k 的矩阵表示。
costs[0][0] 表示第 0 幢房子粉刷成 0 号颜色的成本；costs[1][2] 表示第 1 幢房子粉刷成 2 号颜色的成本，以此类推。返回 粉刷完所有房子的最低成本 。
示例 1：
输入: costs = [[1,5,3],[2,9,4]] 输出: 5 解释: 将房子 0 刷成 0 号颜色，房子 1 刷成 2 号颜色。花费: 1 + 4 = 5; 或者将 房子 0 刷成 2 号颜色，房子 1 刷成 0 号颜色。花费: 3 + 2 = 5.
示例 2:
输入: costs = [[1,3],[2,4]] 输出: 5
提示：
costs.length == ncosts[i].length == k1 <= n <= 1002 <= k <= 201 <= costs[i][j] <= 20
进阶：您能否在 O(nk) 的时间复杂度下解决此问题？
原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 4.3 MB, 提交时间: 2023-10-22 08:27:37
func minCostII(costs [][]int) int {
n := len(costs)
if n == 0 {
return 0
}
k := len(costs[0])
for i := 1; i < n; i++ {
for j := 0; j < k; j++ {
// 选择第 i-1 号房子的方案中，涂色方案不为 j 的花费最小的那个
// 用 minColor(costs[i-1], j) 更新当前第 i 号房子选择 j 涂色方案的最小总花费
costs[i][j] = minColor(costs[i-1], j) + costs[i][j]
}
}
// 返回第 n-1 号房子最小的花费, k+1 是一个遍历时取不到方案
return minColor(costs[n-1], k+1)
}
// 找到当前房子的涂色方案中，不是 nextColor 方案的最小代价
func minColor(colors []int, nextColor int) int {
// 找最小，初始值为最大
res := math.MaxInt64
for i, cost := range colors {
// 遍历 [0,k) 种方案，跳过 nextColor 方案
if i != nextColor {
if res > cost {
res = cost
}
}
}
return res
}
golang 解法, 执行用时: 8 ms, 内存消耗: 4.9 MB, 提交时间: 2023-10-22 08:27:26
import "math"
func minCostII(costs [][]int) int {
if len(costs) == 0 {
return 0
}
n := len(costs)
K := len(costs[0])
//init
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, K)
}
for i := 1; i < n; i++ {
for j := 0; j < K; j++ {
dp[i][j] = math.MaxInt64
}
}
for j := 0; j < K; j++ {
dp[0][j] = costs[0][j]
}
for i := 1; i < n; i++ {
for j := 0; j < K; j++ {
for k := 0; k < K; k++ {
if j == k {
continue
}
dp[i][j] = min(dp[i-1][k]+costs[i][j], dp[i][j])
}
}
}
return min(dp[n-1]...)
}
func min(a ...int) int {
res := math.MaxInt32
for _, v := range a {
if v < res {
res = v
}
}
return res
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 11.9 MB, 提交时间: 2023-10-22 08:26:22
class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
int n = costs.size(), k = costs[0].size();
//dp[i][j] 表示第i 个房子用第j 种颜色的最小花费
vector<vector<int>> dp(n + 1, vector<int>(k, 0));
//c1表示上一个房子粉刷为某种颜色的最低花费, c2表示上一个房子粉刷为某种颜色的第二低花费
int c1 = 0, c2 = 0;
for(int i = 0; i < n; i++){
int tmp1 = 2e9, tmp2 = 2e9;
for(int j = 0; j < k; j++){
int &d = dp[i + 1][j];//d来表示dp[i + 1][j], 代码看起来干净
//如果当前颜色j与上一个房子的花费最小颜色花费不一样，就可以直接去上一个房子颜色的最低花费，与当前花费形成最优解，如果一样，就取上一个房子的第二低花费来形成当前颜色的最优解
if(dp[i][j] != c1) d = costs[i][j] + c1;
else d = costs[i][j] + c2;
//在得到当前房子的最优解时候同时为下一个房子求出最低花费和第二低花费
//就是维护一个最小值，和一个第二小的值
if(d < tmp1) tmp2 = tmp1, tmp1 = d;
else if(d < tmp2) tmp2 = d;
}
c1 = tmp1, c2 = tmp2;//换上新的值
}
return *min_element(dp[n].begin(), dp[n].end());//取第n个房子的最小花费颜色
//return c1;也可以
}
};
python3 解法, 执行用时: 48 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-22 08:26:04
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n = len(costs)
if n == 0: return 0 # 这是一个有效用例。
k = len(costs[0])
# 首先，我们需要确定第一行的两个最低开销。
# 我们还需要记住最低的那个颜色。
prev_min_cost = prev_second_min_cost = prev_min_color = None
for color, cost in enumerate(costs[0]):
if prev_min_cost is None or cost < prev_min_cost:
prev_second_min_cost = prev_min_cost
prev_min_color = color
prev_min_cost = cost
elif prev_second_min_cost is None or cost < prev_second_min_cost:
prev_second_min_cost = cost
# 现在，我们需要一路往下走，维护最小值。
for house in range(1, n):
min_cost = second_min_cost = min_color = None
for color in range(k):
# 确定此单元格的成本(不写入)。
cost = costs[house][color]
if color == prev_min_color:
cost += prev_second_min_cost
else:
cost += prev_min_cost
# 确定当前成本是否也是最低成本。
if min_cost is None or cost < min_cost:
second_min_cost = min_cost
min_color = color
min_cost = cost
elif second_min_cost is None or cost < second_min_cost:
second_min_cost = cost
# 将当前值保存为前一个值。
prev_min_cost = min_cost
prev_min_color = min_color
prev_second_min_cost = second_min_cost
return prev_min_cost
java 解法, 执行用时: 2 ms, 内存消耗: 42.2 MB, 提交时间: 2023-10-22 08:25:47
class Solution {
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
int k = costs[0].length;
int n = costs.length;
/* 首先，我们需要确定第一行的两个最小值。我们还需要记住最小的那个颜色。*/
int prevMin = -1; int prevSecondMin = -1; int prevMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[0][color];
if (prevMin == -1 || cost < prevMin) {
prevSecondMin = prevMin;
prevMinColor = color;
prevMin = cost;
} else if (prevSecondMin == -1 || cost < prevSecondMin) {
prevSecondMin = cost;
}
}
// 现在，我们需要一路往下走，维护最小值。
for (int house = 1; house < n; house++) {
int min = -1; int secondMin = -1; int minColor = -1;
for (int color = 0; color < k; color++) {
// 确定此单元格的成本(不写入)。
int cost = costs[house][color];
if (color == prevMinColor) {
cost += prevSecondMin;
} else {
cost += prevMin;
}
// 确定当前成本是否也是最低成本。
if (min == -1 || cost < min) {
secondMin = min;
minColor = color;
min = cost;
} else if (secondMin == -1 || cost < secondMin) {
secondMin = cost;
}
}
// 将当前 min 转换为以前的 min。
prevMin = min;
prevSecondMin = secondMin;
prevMinColor = minColor;
}
return prevMin;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 42.1 MB, 提交时间: 2023-10-22 08:25:25
class Solution {
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
// 查找上一行中的最小颜色和第二最小颜色。
int minColor = -1; int secondMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[house - 1][color];
if (minColor == -1 || cost < costs[house - 1][minColor]) {
secondMinColor = minColor;
minColor = color;
} else if (secondMinColor == -1 || cost < costs[house - 1][secondMinColor]) {
secondMinColor = color;
}
}
// 现在计算当前行的新成本。
for (int color = 0; color < k; color++) {
if (color == minColor) {
costs[house][color] += costs[house - 1][secondMinColor];
} else {
costs[house][color] += costs[house - 1][minColor];
}
}
}
// 找到最后一行的最小值。
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-22 08:25:08
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n = len(costs)
if n == 0: return 0
k = len(costs[0])
for house in range(1, n):
# 查找上一行中的最小颜色和第二最小颜色。
min_color = second_min_color = None
for color in range(k):
cost = costs[house - 1][color]
if min_color is None or cost < costs[house - 1][min_color]:
second_min_color = min_color
min_color = color
elif second_min_color is None or cost < costs[house - 1][second_min_color]:
second_min_color = color
# 现在计算当前行的新成本。
for color in range(k):
if color == min_color:
costs[house][color] += costs[house - 1][second_min_color]
else:
costs[house][color] += costs[house - 1][min_color]
# 答案将会是最后一行的最小值。
return min(costs[-1])
python3 解法, 执行用时: 116 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-22 08:24:49
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n = len(costs)
if n == 0: return 0
k = len(costs[0])
previous_row = costs[0]
for house in range(1, n):
current_row = [0] * k
for color in range(k):
best = math.inf
for previous_color in range(k):
if color == previous_color: continue
best = min(best, previous_row[previous_color])
current_row[color] += costs[house][color] + best
previous_row = current_row
return min(previous_row)
java 解法, 执行用时: 2 ms, 内存消耗: 41.8 MB, 提交时间: 2023-10-22 08:24:21
class Solution {
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
int k = costs[0].length;
int n = costs.length;
int[] previousRow = costs[0];
for (int house = 1; house < n; house++) {
int[] currentRow = new int[k];
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor) continue;
min = Math.min(min, previousRow[previousColor]);
}
currentRow[color] += costs[house][color] += min;
}
previousRow = currentRow;
}
// 找到最后一行的最小值。
int min = Integer.MAX_VALUE;
for (int c : previousRow) {
min = Math.min(min, c);
}
return min;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 41.9 MB, 提交时间: 2023-10-22 08:24:05
class Solution {
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor) continue;
min = Math.min(min, costs[house - 1][previousColor]);
}
costs[house][color] += min;
}
}
// 找到最后一行的最小值。
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
}
python3 解法, 执行用时: 124 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-22 08:23:48
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n = len(costs)
if n == 0: return 0
k = len(costs[0])
for house in range(1, n):
for color in range(k):
best = math.inf
for previous_color in range(k):
if color == previous_color: continue
best = min(best, costs[house - 1][previous_color])
costs[house][color] += best
return min(costs[-1])
python3 解法, 执行用时: 140 ms, 内存消耗: 17.4 MB, 提交时间: 2023-10-22 08:23:24
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
# 首先定义 n 和 k，以使以下代码更简洁。
n = len(costs)
if n == 0: return 0 # 没有房子是一个有效的测试用例！
k = len(costs[0])
# 如果你不熟悉 lru_cache，因为它是必要的，所以请在文档中查阅它。
@lru_cache(maxsize=None)
def memo_solve(house_num, color):
# 边界条件
if house_num == n - 1:
return costs[house_num][color]
# 递归条件
cost = math.inf
for next_color in range(k):
if next_color == color:
continue # 不能给相邻的房子涂同样的颜色
cost = min(cost, memo_solve(house_num + 1, next_color))
return costs[house_num][color] + cost
# 考虑粉刷 0 号房子的所有选项，找出最小值。
cost = math.inf
for color in range(k):
cost = min(cost, memo_solve(0, color))
return cost
java 解法, 执行用时: 104 ms, 内存消耗: 43 MB, 提交时间: 2023-10-22 08:23:06
class Solution {
private int n;
private int k;
private int[][] costs;
private Map<String, Integer> memo;
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
this.k = costs[0].length;
this.n = costs.length;
this.costs = costs;
this.memo = new HashMap<>();
int minCost = Integer.MAX_VALUE;
for (int color = 0; color < k; color++) {
minCost = Math.min(minCost, memoSolve(0, color));
}
return minCost;
}
private int memoSolve(int houseNumber, int color) {
// 边界条件：后面没有更多的房子了。
if (houseNumber == n - 1) {
return costs[houseNumber][color];
}
// 记忆化搜索情况：我们已经解决这个子问题了吗？
if (memo.containsKey(getKey(houseNumber, color))) {
return memo.get(getKey(houseNumber, color));
}
// 递归条件：决定剩下的最小花费。
int minRemainingCost = Integer.MAX_VALUE;
for (int nextColor = 0; nextColor < k; nextColor++) {
if (color == nextColor) continue;
int currentRemainingCost = memoSolve(houseNumber + 1, nextColor);
minRemainingCost = Math.min(currentRemainingCost, minRemainingCost);
}
int totalCost = costs[houseNumber][color] + minRemainingCost;
memo.put(getKey(houseNumber, color), totalCost);
return totalCost;
}
// 将门牌号和颜色转换为记忆化的简单字符串键。
private String getKey(int n, int color) {
return String.valueOf(n) + " " + String.valueOf(color);
}
}