# Question

Formatted question description: https://leetcode.ca/all/265.html

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 is the cost of painting house 0 with color 0; costs is the cost of painting house 1 with color 2, and so on...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.


Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5


Constraints:

• costs.length == n
• costs[i].length == k
• 1 <= n <= 100
• 2 <= k <= 20
• 1 <= costs[i][j] <= 20

Follow up: Could you solve it in O(nk) runtime?

# Algorithm

### 3 for loops

Use dynamic programming. Create a 2D array dp with n rows and k columns. The element dp[i][j] represents the minimum total cost so far to paint houses 0 to i with the house at index i painted with color j.

For row 0 which corresponds to house 0, dp[j] equals costs[j]. To get dp[i][j] for i > 0, first find the minimum in row dp[i - 1] except dp[i - 1][j], which is represented as min here, since any two adjacent houses must be painted with different colors, then set dp[i][j] = min + costs[i][j].

Finally, find the minimum element from row dp[n - 1] and return the minimum value, which is the minimum cost to paint all houses.

### Follow up: tracking min1 and min2

Finding the minimum value of different colors is not to traverse all the different colors, but to use min1 and min2 to record the smallest and second smallest cost colors

• If the current house color is the same as min1, use the value corresponding to min2 to calculate
• On the contrary, use the value corresponding to min1. This solution actually includes the method of finding the sub-smallest value

# Code

• public class Paint_House_II {

// O(n * k^2)
class Solution_N3 {
public int minCostII(int[][] costs) {
if (costs.length == 0 || costs.length == 0)
return 0;
int length = costs.length, colors = costs.length;
int[][] dp = new int[length][colors];
for (int i = 0; i < colors; i++)
dp[i] = costs[i];
for (int i = 1; i < length; i++) {
for (int j = 0; j < colors; j++) {
int curCost = costs[i][j];
int prevMinSum = Integer.MAX_VALUE;
for (int k = 0; k < colors; k++) {
if (j == k)
continue;
prevMinSum = Math.min(prevMinSum, dp[i - 1][k]);
}
dp[i][j] = prevMinSum + curCost;
}
}
int minCost = Integer.MAX_VALUE;
for (int i = 0; i < colors; i++)
minCost = Math.min(minCost, dp[length - 1][i]);
return minCost;
}
}

public class Solution {
public int minCostII(int[][] costs) {

if(costs != null && costs.length == 0) {
return 0;
}

int prevMin = 0, prevSecondMin = 0, prevIdx = -1;

for(int i = 0; i < costs.length; i++){

int currMin = Integer.MAX_VALUE;
int currSecondMin = Integer.MAX_VALUE;
int currIdx = -1;

for(int j = 0; j < costs.length; j++){ // go over all colors

costs[i][j] = costs[i][j] + (prevIdx == j ? prevSecondMin : prevMin);

if(costs[i][j] < currMin){
currSecondMin = currMin;
currMin = costs[i][j];
currIdx = j;
} else if (costs[i][j] < currSecondMin){
currSecondMin = costs[i][j];
}
}
prevMin = currMin;
prevSecondMin = currSecondMin;
prevIdx = currIdx;
}
return prevMin;
}
}

public class Solution_DP_O_nk {
public int minCostII(int[][] costs) {

if(costs != null && costs.length == 0) {
return 0;
}

int[][] dp = costs;
int min1 = -1, min2 = -1;

for (int i = 0; i < dp.length; i++) {
int last1 = min1;
int last2 = min2;
min1 = -1; min2 = -1;
for (int j = 0; j < dp[i].length; j++) {
if (j != last1) {
dp[i][j] += last1 < 0 ? 0 : dp[i - 1][last1];
} else {
dp[i][j] += last2 < 0 ? 0 : dp[i - 1][last2];
}

if (min1 < 0 || dp[i][j] < dp[i][min1]) {
min2 = min1;
min1 = j;
} else if (min2 < 0 || dp[i][j] < dp[i][min2]) {
min2 = j;
}
}
}

return dp[dp.length - 1][min1];
}
}
}

############

class Solution {
public int minCostII(int[][] costs) {
int n = costs.length, k = costs.length;
int[] f = costs.clone();
for (int i = 1; i < n; ++i) {
int[] g = costs[i].clone();
for (int j = 0; j < k; ++j) {
int t = Integer.MAX_VALUE;
for (int h = 0; h < k; ++h) {
if (h != j) {
t = Math.min(t, f[h]);
}
}
g[j] += t;
}
f = g;
}
return Arrays.stream(f).min().getAsInt();
}
}

• class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
int n = costs.size(), k = costs.size();
vector<int> f = costs;
for (int i = 1; i < n; ++i) {
vector<int> g = costs[i];
for (int j = 0; j < k; ++j) {
int t = INT_MAX;
for (int h = 0; h < k; ++h) {
if (h != j) {
t = min(t, f[h]);
}
}
g[j] += t;
}
f = move(g);
}
return *min_element(f.begin(), f.end());
}
};

• class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n, k = len(costs), len(costs)
f = costs[:] # 1st house
for i in range(1, n):
g = costs[i][:]
for j in range(k):
t = min(f[h] for h in range(k) if h != j)
g[j] += t
f = g
return min(f)

class Solution: # min1, min2
def minCostII(self, costs):
if not costs or len(costs) == 0:
return 0

prev_min = 0
prev_second_min = 0
prev_idx = -1

for i in range(len(costs)):
curr_min = float('inf')
curr_second_min = float('inf')
curr_idx = -1

for j in range(len(costs)):
costs[i][j] = costs[i][j] + (prev_idx == j) * prev_second_min + (prev_idx != j) * prev_min

if costs[i][j] < curr_min:
curr_second_min = curr_min
curr_min = costs[i][j]
curr_idx = j
elif costs[i][j] < curr_second_min:
curr_second_min = costs[i][j]

prev_min = curr_min
prev_second_min = curr_second_min
prev_idx = curr_idx

return prev_min

############

class Solution(object):
def minCostII(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if not costs:
return 0
dp = [ * len(costs) for _ in range(0, len(costs))]
dp = costs
for i in range(1, len(costs)):
for j in range(0, len(costs)):
dp[i][j] = min(dp[i - 1][:j] + dp[i - 1][j + 1:]) + costs[i][j] # exclude j itself
return min(dp[-1])


• func minCostII(costs [][]int) (ans int) {
n, k := len(costs), len(costs)
f := cp(costs)
for i := 1; i < n; i++ {
g := cp(costs[i])
for j := 0; j < k; j++ {
t := math.MaxInt32
for h := 0; h < k; h++ {
if h != j && t > f[h] {
t = f[h]
}
}
g[j] += t
}
f = g
}
ans = f
for _, v := range f {
if ans > v {
ans = v
}
}
return
}

func cp(arr []int) []int {
t := make([]int, len(arr))
copy(t, arr)
return t
}