Paint House 解答

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);
    }
}