Question
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3
cost matrix. For example, costs[0][0]
is the cost of painting house 0 with color red;costs[1][2]
is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.
Note:
All costs are positive integers.
Solution
拿到这题的第一反应是画出解空间树。我们用1, 2, 3分别代表red, green, blue
()
/ | \
1 2 3
/ \ / \ / \
2 3 1 3 1 2
……………….
粗暴的方法是用DFS遍历整个解空间树。但是我们可以看到在每一层,其实有重复计算。
所以这题的思路和那道经典的求min path sum一样,是用DP。Time complexity O(n), space cost O(1)
cost1, cost2, cost3表示第n层选了1/2/3后的最少话费。
举个例子:
red green blue
h1 1 2 3
h2 3 1 2
h3 4 3 2
我们从底向上遍历做DP
对于h3这一层:
cost1 = 4, cost2 = 3, cost3 = 2
对于h2这一层:
cost1′ = 3 + min(cost2, cost3) = 5, cost2′ = 1 + min(cost1, cost3) = 3, cost3′ = 2 + min(cost1, cost2) = 5
对于h1这一层:
cost1” = 1 + min(cost2′, cost3′) = 4, cost2” = 2 + min(cost1′, cost3′) = 7, cost3” = 3 + min(cost1′, cost2′) = 6
因此最少话费是cost1”
public class Solution {
public int minCost(int[][] costs) {
if (costs == null || costs.length < 1) {
return 0;
}
int m = costs.length, n = costs[0].length;
int cost1 = costs[m - 1][0], cost2 = costs[m - 1][1], cost3 = costs[m - 1][2];
for (int i = m - 2; i >= 0; i--) {
int tmp1 = cost1, tmp2 = cost2, tmp3 = cost3;
cost1 = costs[i][0] + Math.min(tmp2, tmp3);
cost2 = costs[i][1] + Math.min(tmp1, tmp3);
cost3 = costs[i][2] + Math.min(tmp1, tmp2);
}
int result = Math.min(cost1, cost2);
return Math.min(result, cost3);
}
}