[LeetCode]Paint House

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

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

那么对于这道题，k = 3。并且我们可以用滚动数组把空间优化到常数，时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int minCost(vector<vector<int>>& costs) {
	int len = costs.size();
	vector<int> dp(3, 0);
	for (int i = 0; i < len; ++i)
	{
	int cost1 = 0, cost2 = 0, cost3 = 0;
	cost1 = costs[i][0] + min(dp[1], dp[2]);
	cost2 = costs[i][1] + min(dp[0], dp[2]);
	cost3 = costs[i][2] + min(dp[0], dp[1]);
	dp[0] = cost1;
	dp[1] = cost2;
	dp[2] = cost3;
	}
	return min(dp[0], min(dp[1], dp[2]));
	}
	};

view raw Paint House.cpp hosted with ❤ by GitHub