# Simple Python DP Solution (w/ Explanation) 44ms :O

• 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`, `F_Green`, `F_Blue`.

``````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_Green` and `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 `F_Blue` and `F_Green`).

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[0] = min cost when ith house painted with red
F[1] = min cost when ith house painted with blue
F[2] = min cost when ith house painted with green
"""
F = costs[0][:]
new = [0]*3

for i in range(1, len(costs)):
new[0] = min(F[1], F[2]) + costs[i][0]
new[1] = min(F[0], F[2]) + costs[i][1]
new[2] = min(F[0], F[1]) + costs[i][2]
F = new[:]

return min(F)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.