05 August 2008
二维数组中给每个房子涂色，共三种颜色，二维数组中的数字代表涂色的价格，涂完所有房子并且相邻房子颜色不同同时总价格最低
Example 1:
1
2
3
4
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.
Example 2:
1
2
Input: costs = []
Output: 0
Example 3:
1
2
Input: costs = [[7,6,2]]
Output: 2
Constraints:
1
costs.length == n
1
costs[i].length == 3
1
0 <= n <= 100
1
1 <= costs[i][j] <= 20
记忆化搜索
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
class Solution {
private int[][] costs;
private Map<String, Integer> memo;
public int minCost(int[][] costs) {
if (costs.length == 0) {
return 0;
}
this.costs = costs;
this.memo = new HashMap<>();
return Math.min(paintCost(0, 0), Math.min(paintCost(0, 1), paintCost(0, 2)));
}
private int paintCost(int n, int color) {
if (memo.containsKey(getKey(n, color))) {
return memo.get(getKey(n, color));
}
int totalCost = costs[n][color];
if (n == costs.length - 1) {
} else if (color == 0) { // Red
totalCost += Math.min(paintCost(n + 1, 1), paintCost(n + 1, 2));
} else if (color == 1) { // Green
totalCost += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 2));
} else { // Blue
totalCost += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 1));
}
memo.put(getKey(n, color), totalCost);
return totalCost;
}
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
class Solution {
public int minCost(int[][] costs) {
for (int n = costs.length - 2; n >= 0; n--) {
// Total cost of painting the nth house red.
costs[n][0] += Math.min(costs[n + 1][1], costs[n + 1][2]);
// Total cost of painting the nth house green.
costs[n][1] += Math.min(costs[n + 1][0], costs[n + 1][2]);
// Total cost of painting the nth house blue.
costs[n][2] += Math.min(costs[n + 1][0], costs[n + 1][1]);
}
if (costs.length == 0) return 0;
return Math.min(Math.min(costs[0][0], costs[0][1]), costs[0][2]);
}
}
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
/* This code OVERWRITES the input array! */
class Solution {
public int minCost(int[][] costs) {
if (costs.length == 0) return 0;
int[] previousRow = costs[costs.length -1];
for (int n = costs.length - 2; n >= 0; n--) {
/* PROBLEMATIC CODE IS HERE
* This line here is NOT making a copy of the original, it's simply
* making a reference to it Therefore, any writes into currentRow
* will also be written into "costs". This is not what we wanted!
*/
int[] currentRow = costs[n];
// Total cost of painting the nth house red.
currentRow[0] += Math.min(previousRow[1], previousRow[2]);
// Total cost of painting the nth house green.
currentRow[1] += Math.min(previousRow[0], previousRow[2]);
// Total cost of painting the nth house blue.
currentRow[2] += Math.min(previousRow[0], previousRow[1]);
previousRow = currentRow;
}
return Math.min(Math.min(previousRow[0], previousRow[1]), previousRow[2]);
}
}