[Locked] Paint House I & II

Paint House

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.

分析:

  典型动态规划,通过遍历所有情况可以弥补前面的选择对后面的影响。时间复杂度为O(n*3*3) = O(n);利用滚动数组,空间复杂度为O(3*2) = O(1)。

代码:

int minCost2(vector<vector<int> > cost) {
vector<int> opt(, ), temp(, );
for(int i = ; i < cost.size(); i++) {
for(int j = ; j < ; j++) {
temp[j] = INT_MAX;
for(int k = ; k < ; k++) {
if(j != k)
temp[j] = min(temp[j], opt[k] + cost[i][j]);
}
}
opt.swap(temp);
}
int minc = INT_MAX;
for(int i : opt)
minc = min(minc ,i);
return minc;
}

Paint House II

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.

Follow up:
Could you solve it in O(nk) runtime?

分析:

  如果采用I中的方法,时间复杂度为O(n*k*k),空间复杂度为O(k*2)。为了降低时间复杂度,可以通过减少两重k循环里的大量重复计算来使得O(k*k)的复杂度变为O(k)。此题中,对于j = j1, j2两种情况,它们的内部k循环有k-2次是重复比较了cost[i][j1] + x和cost[i][j2] + x的大小的,可以通过一次cost[i][j1]和cost[i][j2]的比较替代;扩展到j = 1...k种情况,只需找到小的cost[i][j], j = 1...k.

解法:

  动态规划,第i轮的最小代价是j = j1时,假设第i + 1轮中,j = j1是默认剔除的,很简单,前一轮的结果后一轮的最小结果都应该使用的,那么第i + 1轮的最小代价是min(cost[i+1][j])的j的取值时;然而j = j1并不是默认剔除的,故在第i + 1轮是cost[i + 1][j1]是无法使用上一轮的最小结果的,但它应该使用第二小的结果,故只需要比较第i + 1轮中,j == j1和j != j1两种情况的值即可。时间复杂度为O(n*(k + 常数)) = O(nk),空间复杂度,利用滚动值存储中间结果,为O(1)

代码:

int minCost(vector<vector<int> > cost) {
int min1 = , min2 = , record = -, c = INT_MAX;
for(int i = ; i < cost.size(); i++) {
int minval1 = INT_MAX, minval2 = INT_MAX, last = -;
for(int j = ; j < cost[].size(); j++) {
if(record != j) {
if(minval1 > cost[i][j]) {
minval2 = minval1;
minval1 = cost[i][j];
last = j;
}
else
minval2 = min(minval2, cost[i][j]);
}
}
int a = minval1 + min1, b = minval2 + min1;
if(record != -)
c = cost[i][record] + min2;
if(a < c) {
record = last;
min1 = a;
min2 = min(b, c);
}
else {
min1 = c;
min2 = a;
} }
cout<<endl;
return min1;
}
上一篇:在asp.net利用jquery.MultiFile实现多文件上传(转载)


下一篇:linux中ONBOOT=yes的含义