I believe the solution is similar to some of the other solutions posted here.
Simply put, the problem can be imagined as finding the minimum price of painting
x houses where the
xth house is painted in one of the three colors: red, blue or green. The minimum price here would be
min(X-red, X-blue, X-green), i.e. minimum of the prices when the
xth house is painted in one of red, blue or green.
We simply create our state equations
F_Red' = min(F_Blue, F_Green) + costs[x][Red] F_Blue' = min(F_Red, F_Green) + costs[x][Blue] F_Green' = min(F_Red, F_Blue) + costs[x][Green]
F_Red' is the new value of
F_Red based on
F_Blue of the previous house. The cost is essentially the minimum of the cost to paint the previous house either blue or green plus the cost of painting the current house red. Obviously, for implementation purposes one would need to cache the value of
F_Red before changing it as it is needed in subsequent state equations (similarly for
Here's the Python code for the same:
class Solution(object): def minCost(self, costs): """ :type costs: List[List[int]] :rtype: int """ if not costs: return 0 """ F function essentially holds the minimum value of the ith house painted with each color. F = min cost when ith house painted with red F = min cost when ith house painted with blue F = min cost when ith house painted with green """ F = costs[:] new = *3 for i in range(1, len(costs)): new = min(F, F) + costs[i] new = min(F, F) + costs[i] new = min(F, F) + costs[i] F = new[:] return min(F)