# Question

Formatted question description: https://leetcode.ca/all/256.html

 256	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 is the cost of painting house 0 with color red;
costs is the cost of painting house 1 with color green, and so on...

Find the minimum cost to paint all houses.

Example:

Given costs = [[14,2,11],[11,14,5],[14,3,10]]
return 10

house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10

Note:
All costs are positive integers.



# Algorithm

Two-dimensional dynamic array dp, where dp[i][j] represents the minimum cost of brushing to the i+1th house with color j, and the state transition equation is:

dp[i][j] = cost[i][j] + min(dp[i-1][(j + 1)% 3], dp[i-1][(j + 2)% 3])

# Code

Java

• 
public class Paint_House {

public class Solution {
public int minCost(int[][] costs) {
int len = costs.length;

if(costs != null && len == 0) {
return 0;
}

int[][] dp = costs; // dp[i][j], for house-i, three colors j (0 or 1 or 2)

// no need dp[m+1][n+1], just i=1 is good enough
for(int i = 1; i < len; i++){
dp[i] = costs[i] + Math.min(costs[i - 1], costs[i - 1]);
dp[i] = costs[i] + Math.min(costs[i - 1], costs[i - 1]);
dp[i] = costs[i] + Math.min(costs[i - 1], costs[i - 1]);
}

return Math.min(dp[len - 1], Math.min(dp[len - 1], dp[len - 1]));
}
}
}

• // OJ: https://leetcode.com/problems/paint-house/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
for (int i = 1; i < costs.size(); ++i) {
for (int j = 0; j < 3; ++j) costs[i][j] += min(costs[i - 1][(j + 1) % 3], costs[i - 1][(j + 2) % 3]);
}
return *min_element(costs.back().begin(), costs.back().end());
}
};

• class Solution:
def minCost(self, costs: List[List[int]]) -> int:
a = b = c = 0
for ca, cb, cc in costs:
a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc
return min(a, b, c)

############

class Solution(object):
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if not costs:
return 0
dp =  * (len(costs))
dp[:] = costs
for i in range(1, len(costs)):
d0 = d1 = d2 = 0
for j in range(0, 3):
if j == 0:
d0 = min(dp, dp) + costs[i]
elif j == 1:
d1 = min(dp, dp) + costs[i]
else:
d2 = min(dp, dp) + costs[i]
dp, dp, dp = d0, d1, d2
return min(dp)