LeetCode Q256: 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.

Solution:

	class Solution {
	public:
	int minCost(vector<vector<int>>& costs) {
	int houseNum = costs.size();
	vector<vector<int> > totalCosts(houseNum+1, vector<int>(3, 0));
	for(int i=1; i<totalCosts.size(); i++){
	totalCosts[i][0]=min(totalCosts[i-1][1]+costs[i-1][0], totalCosts[i-1][2]+costs[i-1][0]);
	totalCosts[i][1]=min(totalCosts[i-1][0]+costs[i-1][1], totalCosts[i-1][2]+costs[i-1][1]);
	totalCosts[i][2]=min(totalCosts[i-1][0]+costs[i-1][2], totalCosts[i-1][1]+costs[i-1][2]);
	}
	int minCost = min(totalCosts[houseNum][0], min(totalCosts[houseNum][1], totalCosts[houseNum][2]));
	return minCost;
	}
	};

view raw Q256PaintHouses.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int minCost(vector<vector<int>>& costs) {
	int res=0;
	vector<int> cost(3, 0);
	if(costs.empty())
	return res;
	for(int i=0; i<costs.size(); i++){
	vector<int> tmp(3, 0);
	tmp[0] = min(cost[1]+costs[i][0], cost[2]+costs[i][0]);
	tmp[1] = min(cost[0]+costs[i][1], cost[2]+costs[i][1]);
	tmp[2] = min(cost[0]+costs[i][2], cost[1]+costs[i][2]);
	cost = tmp;
	}
	return min(cost[0], min(cost[1], cost[2]));
	}
	};

view raw Q256Rnd2.cpp hosted with ❤ by GitHub