A simple Python DP solution without too many decoration


  • 0
    class Solution(object):
        def minCost(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            #dp[i][j] is ith house with color j, dp[i - 1][x] + costs[i][j] for x in 0,1,2 and x != j
            if not costs:
                return 0
            dp = [ [0xffffffff for i in xrange(3) ] for j in xrange(len(costs)) ]
            for i in xrange(len(costs)):
                for j in xrange(3):
                    if i == 0:
                        dp[i][j] = costs[0][j]
                    else:
                        for x in xrange(3):
                            if x != j:
                                dp[i][j] = min(dp[i][j], dp[i - 1][x] + costs[i][j])
            return min(dp[len(costs) - 1])
    

Log in to reply
 

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