# Python DP solution, O(n) time, O(1) space

• the idea is to store current house's minimum cost in different colors.

``````def minCost(self, costs):
size = len(costs)
if size == 0:
return 0

pre = costs[0][:]
now = [0]*3

for i in xrange(size-1):
now[0] = min(pre[1], pre[2]) + costs[i+1][0]
now[1] = min(pre[0], pre[2]) + costs[i+1][1]
now[2] = min(pre[0], pre[1]) + costs[i+1][2]
pre[:] = now[:]

return min(pre)``````

• This is beautiful.
I came up with Back Tracking and store all paths which was also accepted,
but I read your solution and realized that only I needed to do is store the latest bit of colors!

Thanks:)

My Code:

``````   class Path(object):
def __init__(self, history, cost, lastColor):
self.history = history
self.cost = cost
self.lastColor = lastColor

class Solution(object):
def minCost(self, costs):
costLen = len(costs)
if costLen == 0:
return 0

paths = []
costMap = {}
for i in range(0, costLen):
if i == 0:
path0 = Path([0], costs[0][0], 0)
path1 = Path([1], costs[0][1], 1)
path2 = Path([2], costs[0][2], 2)
paths = [path0, path1, path2]
continue

newPaths = []
costCompareMap = {} #{lastColor, Path}
for path in paths:
# candidate = 1 or 2 if lastColor = 0,
# candidate = 2 or 0 if lastColor = 1,
# candidate = 0 or 1 if lastColor = 2
candidates = [x for x in [0,1,2] if x != path.lastColor]
for candidate in candidates:
newHistory = path.history + [candidate]
newCost = path.cost + costs[i][candidate]
newPath = Path(newHistory, newCost, candidate)

# If a color of last painted house is the same, we can consider only the lowest cost one.
if candidate in costCompareMap:
existingPath = costCompareMap[candidate]
if existingPath.cost > newCost:
newPaths.remove(costCompareMap[candidate])
newPaths.append(newPath)
else:
costCompareMap[candidate] = newPath
newPaths.append(newPath)
paths = newPaths

minCost = None
for path in paths:
if not minCost:
minCost = path.cost
elif minCost > path.cost:
minCost = path.cost
return minCost
``````

• This is an elegant solution. Thanks

• We have pretty much the same solution. I cut down the code a little bit. Basically I just store the minimum cost house that ends in either red blue or green and update it accordingly.

``````class Solution(object):
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
min_red, min_blue, min_green = (0,)*3

for house_color_costs in costs:
r, b, g = house_color_costs
min_red, min_blue, min_green = min(min_blue, min_green) + r, min(min_red, min_green) + b, min(min_red, min_blue) + g

return min(min_red, min_blue, min_green)``````

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