05 August 2008
相比256題，这个共有k种颜色可以涂色
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 1
n x k
1
costs[0][0]
1
costs[1][2]
Note:
All costs are positive integers.
Example:
1
2
3
4
Input: [[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.
Follow up:
Could you solve it in O(nk) runtime?
记忆化搜索
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
41
42
43
44
45
46
47
48
49
class Solution {
private int n;
private int k;
private int[][] costs;
private Map<String, Integer> memo;
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
this.k = costs[0].length;
this.n = costs.length;
this.costs = costs;
this.memo = new HashMap<>();
int minCost = Integer.MAX_VALUE;
for (int color = 0; color < k; color++) {
minCost = Math.min(minCost, memoSolve(0, color));
}
return minCost;
}
private int memoSolve(int houseNumber, int color) {
// Base case: There are no more houses after this one.
if (houseNumber == n - 1) {
return costs[houseNumber][color];
}
// Memoization lookup case: Have we already solved this subproblem?
if (memo.containsKey(getKey(houseNumber, color))) {
return memo.get(getKey(houseNumber, color));
}
// Recursive case: Determine the minimum cost for the remainder.
int minRemainingCost = Integer.MAX_VALUE;
for (int nextColor = 0; nextColor < k; nextColor++) {
if (color == nextColor) continue;
int currentRemainingCost = memoSolve(houseNumber + 1, nextColor);
minRemainingCost = Math.min(currentRemainingCost, minRemainingCost);
}
int totalCost = costs[houseNumber][color] + minRemainingCost;
memo.put(getKey(houseNumber, color), totalCost);
return totalCost;
}
// Convert a house number and color into a simple string key for the memo.
private String getKey(int n, int color) {
return String.valueOf(n) + " " + String.valueOf(color);
}
}
朴素DP
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
class Solution {
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
int k = costs[0].length;
int n = costs.length;
for (int house = 1; house < n; house++) {
for (int color = 0; color < k; color++) {
int min = Integer.MAX_VALUE;
for (int previousColor = 0; previousColor < k; previousColor++) {
if (color == previousColor) continue;
min = Math.min(min, costs[house - 1][previousColor]);
}
costs[houseNumber][color] += min;
}
}
// Find the minimum in the last row.
int min = Integer.MAX_VALUE;
for (int c : costs[n - 1]) {
min = Math.min(min, c);
}
return min;
}
}
DP + 时间空间优化
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
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public int minCostII(int[][] costs) {
if (costs.length == 0) return 0;
int k = costs[0].length;
int n = costs.length;
/* Firstly, we need to determine the 2 lowest costs of
* the first row. We also need to remember the color of
* the lowest. */
int prevMin = -1; int prevSecondMin = -1; int prevMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[0][color];
if (prevMin == -1 || cost < prevMin) {
prevSecondMin = prevMin;
prevMinColor = color;
prevMin = cost;
} else if (prevSecondMin == -1 || cost < prevSecondMin) {
prevSecondMin = cost;
}
}
// And now, we need to work our way down, keeping track of the minimums.
for (int house = 1; house < n; house++) {
int min = -1; int secondMin = -1; int minColor = -1;
for (int color = 0; color < k; color++) {
// Determine the cost for this cell (without writing it in).
int cost = costs[house][color];
if (color == prevMinColor) {
cost += prevSecondMin;
} else {
cost += prevMin;
}
// Determine whether or not this current cost is also a minimum.
if (min == -1 || cost < min) {
secondMin = min;
minColor = color;
min = cost;
} else if (secondMin == -1 || cost < secondMin) {
secondMin = cost;
}
}
// Transfer current mins to be previous mins.
prevMin = min;
prevSecondMin = secondMin;
prevMinColor = minColor;
}
return prevMin;
}
}