Problem

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 a n x k cost matrix. 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… Find the minimum cost to paint all houses.

Examples

Example 1

1
2
3
4
5

Input:
costs =[[14,2,11],[11,14,5],[14,3,10]]
Output: 10
Explanation:
The three house use color [1,2,1] for each house. The total cost is 10.

Example 2

1
2
3
4
5

Input:
costs =[[5]]
Output: 5
Explanation:
There is only one color and one house.

Challenge

Could you solve it in O(n*k).

Constraints

All costs are positive integers.

Solution

This problem is similar to Paint House 1 - N houses with 3 colors with no two adjacent houses with same color, but with k colors instead of 3.

Method 1 - Recursion

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {

	public int minCostII(int[][] costs) {
		return minCostRecursive(costs, 0, -1);
	}

	private int helper(int[][] costs, int house, int lastColor) {
		if (house == costs.length) {
			return 0;
		}

		int min = Integer.MAX_VALUE;

		for (int color = 0; color < costs[0].length; color++) {
			if (color != lastColor) {
				int cost = costs[house][color] + helper(costs, house + 1, color);
				min = Math.min(min, cost);
			}
		}

		return min;
	}
}

Method 2 - Top Down DP

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Solution {

	private Integer[][] memo;

	public int minCostII(int[][] costs) {
		memo = new Integer[costs.length][costs[0].length];
		return minCostRecursive(costs, 0, -1);
	}

	private int helper(int[][] costs, int house, int lastColor) {
		if (house == costs.length) {
			return 0;
		}

		if (lastColor != -1 && memo[house][lastColor] != null) {
			return memo[house][lastColor];
		}

		int min = Integer.MAX_VALUE;

		for (int color = 0; color < costs[0].length; color++) {
			if (color != lastColor) {
				int cost = costs[house][color] + helper(costs, house + 1, color);
				min = Math.min(min, cost);
			}
		}

		if (lastColor != -1) {
			memo[house][lastColor] = min;
		}

		return min;
	}
}

Method 3 - DP

This is a classic back pack problem.   - Define dp[n][k], where dp[i][j] means for house i with color j the minimum cost.   - Initial value: dp[0][j] = costs[0][j]. For others, dp[i][j] = Integer.MAX_VALUE;, i >= 1  - Transit function: dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + cost[i][j]), where k != j.  - Final state: Min(dp[n-1][k]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public int minCostII(int[][] costs) {
	if (costs == null || costs.length == 0) {
		return 0;
	}

	int n = costs.length;
	int k = costs[0].length;

	// dp[i][j] means the min cost painting for house i, with color j
	int[][] dp = new int[n][k];

	// Initialize the first row of the DP table with the costs of painting the first house with each color
	for (int color = 0; color < k; color++) {
		dp[0][color] = costs[0][color];
	}

	for (int house = 1; house < n; house++) {
		for (int color = 0; color < k; color++) {
			dp[house][color] = costs[house][color] + findMin(dp[house - 1], color);
		}
	}

	// Final state
	int minCost = Integer.MAX_VALUE;

	for (int i = 0; i < k; i++) {
		minCost = Math.min(minCost, dp[n - 1][i]);
	}

	return minCost;
}

Complexity

  • ⏰ Time complexity: O(n*k*k)
  • 🧺 Space complexity: O(n*k)

Method 4 - Space Optimized DP

Since dp[i][k] only depends on dp[i-1][j], we can use a 1-D DP solution.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public int minCostII(int[][] costs) {
	if (costs == null || costs.length == 0) {
		return 0;
	}
	 
	int n = costs.length;
	int k = costs[0].length;
	 
	// dp[j] means the min cost for color j
	int[] dp1 = new int[k];
	int[] dp2 = new int[k];
	 
	// Initialization
	for (int i = 0; i < k; i++) {
		dp1[i] = costs[0][i];
	}
	 
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < k; j++) {
			dp2[j] = Integer.MAX_VALUE;
			for (int m = 0; m < k; m++) {
				if (m != j) {
					dp2[j] = Math.min(dp1[m] + costs[i][j], dp2[j]);
				}
			}
		}
		 
		for (int j = 0; j < k; j++) {
			dp1[j] = dp2[j];
		}
	}
	 
	// Final state
	int minCost = Integer.MAX_VALUE;
	for (int i = 0; i < k; i++) {
		minCost = Math.min(minCost, dp1[i]);
	}
	 
	return minCost;
}

Complexity

  • ⏰ Time complexity: O(n*k*k)
  • 🧺 Space complexity: O(k)