题目描述
There is a row of n houses, where each house can be painted one of 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 the 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.
样例
Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.
算法1
Linear DP
DP states DP[i, j]: min cost to paint the color j (red, blue or green) on the first ith house
Formula: DP[i, jr] = min(DP[i-1, jb), DP[i-1,jg]) + w[i,jr]
Since we can’t paint the same color on adjcent houses, it can only come from costs from different color
We can reuse the input array, but we need to understand that we change the input array from cost of color j on house i to the min cost of color j on all the first i houses
The answer is the min of the last house, need to consider edge case of only one house.
时间复杂度
O(n)
JAVA 代码
public int minCost(int[][] costs) {
int n = costs.length;
if (n == 0) return 0;
if (n == 1) return Math.min(costs[0][0], Math.min(costs[0][1], costs[0][2]));
for (int i = 1; i < n; i++) {
costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
}
return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2]));
}