Description
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 *n* x *k*
cost matrix. For example, costs[0][0]
is the cost of painting house 0 with color 0; costs[1][2]
is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.
Note:
All costs are positive integers.
Example:
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?
Solution
DP, O(nk), S(nk)
這道題的思路就是在"Paint House"基礎(chǔ)上進(jìn)行擴(kuò)展乳乌,將3維擴(kuò)展到k維上柳恐,時間復(fù)雜度為O(n * k ^ 2)事格。
想降低時間復(fù)雜度也很簡單,只要優(yōu)化getMinExcept(int[] nums, int exceptIndex)即可玄帕。方法是預(yù)處理,記錄minIndex和secondMinIndex想邦。
class Solution {
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
int n = costs.length;
// imporant to handle it here or getMinIndex might return -1
if (n == 1) {
return min(costs[0]);
}
int k = costs[0].length;
int[][] costSum = new int[n + 1][k];
for (int i = 0; i < n; ++i) {
int[] arr = getFirstAndSecondMinIndexes(costSum[i]);
for (int j = 0; j < k; ++j) {
costSum[i + 1][j] = costs[i][j]
+ (j != arr[0]
? costSum[i][arr[0]] : costSum[i][arr[1]]);
}
}
return min(costSum[n]);
}
private int[] getFirstAndSecondMinIndexes(int[] nums) {
int[] res = new int[2];
Arrays.fill(res, -1);
for (int i = 0; i < nums.length; ++i) {
if (res[0] < 0 || nums[i] <= nums[res[0]]) {
res[1] = res[0];
res[0] = i;
} else if (res[1] < 0 || nums[i] < nums[res[1]]) {
res[1] = i;
}
}
return res;
}
private int min(int[] nums) {
int min = Integer.MAX_VALUE;
for (int n : nums) {
min = Math.min(n, min);
}
return min;
}
}
DP, O(nk), S(1)
可以將costs的值做修改裤纹,改成costSum。這樣就不需要新開辟空間啦案狠。
注意一些edge case的處理服傍,例如[[1],[3]]這種钱雷,不可能fill成功的,直接返回MAX_VALUE吹零。否則運行到后面min1一直為-1罩抗,會拋IndexOutOfBoundException。
class Solution {
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0].length == 0) {
return 0;
}
int n = costs.length;
int k = costs[0].length;
if (n > 1 && k < 2) {
return Integer.MAX_VALUE; // impossible to fill
}
int min0 = -1;
int min1 = -1;
for (int i = 0; i < n; ++i) {
int currMin0 = -1;
int currMin1 = -1;
for (int j = 0 ; j < k; ++j) {
if (i > 0) {
costs[i][j] += min0 != j
? costs[i - 1][min0] : costs[i - 1][min1];
}
if (currMin0 < 0 || costs[i][j] < costs[i][currMin0]) {
currMin1 = currMin0;
currMin0 = j;
} else if (currMin1 < 0
|| costs[i][j] < costs[i][currMin1]) {
currMin1 = j;
}
}
min0 = currMin0;
min1 = currMin1;
}
return costs[n - 1][min0];
}
}