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


  • 1
    P

    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)

Log in to reply
 

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