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]
                        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.