Back to all solutions
#265 - Paint House II
Problem Description
There are a row of n houses, each house can be painted with one of the k colors. 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 an n x k cost matrix costs.
- For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on...
Return the minimum cost to paint all houses.
Solution
/**
* @param {number[][]} costs
* @return {number}
*/
var minCostII = function(costs) {
const n = costs.length;
const k = costs[0].length;
let prev = [...costs[0]];
for (let i = 1; i < n; i++) {
const curr = new Array(k);
let min1 = Infinity;
let min2 = Infinity;
let index = -1;
for (let j = 0; j < k; j++) {
if (prev[j] < min1) {
min2 = min1;
min1 = prev[j];
index = j;
} else if (prev[j] < min2) {
min2 = prev[j];
}
}
for (let j = 0; j < k; j++) {
curr[j] = costs[i][j] + (j === index ? min2 : min1);
}
prev = curr;
}
return Math.min(...prev);
};