[LeetCode]Paint House II

用DP[i][k]代表第i个房子用第k个颜色paint情况下，总的cost最小的值。那么我们有递推公式：

• DP[i][k] = cost[i][k] + min(DP[i - 1][j]), where j != k

我们当然可以用滚动数组来优化，但是这样的话对于n * k个值，每一个值我们要k的时间去求min(DP[i - 1][j])，时间复杂度是O(n * k ^ 2)。我们还可以继续优化，其实对于每一个k来说，我们从之前的房子所需要的值只有之前房子的最小cost并且最小cost对应的color不为k，假设color为k，我们就取第二小的值。也就是说，我们只需要维护从上一个房子得到的最小cost，第二小cost和他们对应的color就可以了。这两个值我们在求DP[i][0->k]的时候就可以一直维护，所以总的时间按复杂度可以降低到O(n * k)，常数空间。代码如下：

	class Solution {
	public:
	int minCostII(vector<vector<int>>& costs) {
	int m = costs.size(), n = m ? costs[0].size() : 0;
	int min1 = 0, min2 = 0, color1 = -1, color2 = -1;
	for (int i = 0; i < m; ++i)
	{
	int currMin1 = INT_MAX, currMin2 = INT_MAX, currColor1 = -1, currColor2 = -1;
	for (int j = 0; j < n; ++j)
	{
	int currCost = j != color1 ? min1 + costs[i][j] : min2 + costs[i][j];
	if (currCost < currMin1)
	{
	currMin2 = currMin1;
	currColor2 = currColor1;
	currMin1 = currCost;
	currColor1 = j;
	}
	else if (currCost < currMin2)
	{
	currMin2 = currCost;
	currColor2 = j;
	}
	}
	min1 = currMin1;
	min2 = currMin2;
	color1 = currColor1;
	color2 = currColor2;
	}
	return min1;
	}
	};

view raw Paint House II.cpp hosted with ❤ by GitHub