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


  • 11
    A

    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)

  • 0

    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
    

  • 0
    S

    This is an elegant solution. Thanks


  • 2
    A

    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)

Log in to reply
 

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