Easy to understand Python - beats 96%


  • 0
    S

    The idea is to first derive what is the minimum cost for painting the current house as 'RED', 'BLUE' or 'GREEN' and then using that information to derive the minimum cost to paint the house.

    class Solution(object):
        def minCost(self, costs):
            if not costs: return 0
            dp = costs[0]
            for i in xrange(1, len(costs)):
                currRed, currBlue, currGreen = costs[i][0], costs[i][1], costs[i][2]
                prevRed, prevBlue, prevGreen = dp
                dp = [
                    min(currRed+prevBlue, currRed+prevGreen), # cost if current house is painted red
                    min(currBlue+prevRed, currBlue+prevGreen), # cost if current house is painted blue
                    min(currGreen+prevRed, currGreen + prevBlue) # cost if current house is painted green
                ]
    
            return min(dp)
    

    Without explanation, the basic program looks like

    class Solution(object):
        def minCost(self, costs):
            dp = costs[0]
            for i in xrange(1, len(costs)):
                dp = [min(costs[i][0] + dp[1], costs[i][0] + dp[2]), min(costs[i][1] + dp[0], costs[i][1] + dp[2]), min(costs[i][2] + dp[0], costs[i][2] + dp[1])]
            return min(dp)
    

Log in to reply
 

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