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
```