Python O(nk) beat 95% solution with explaination


  • 2
    K
    class Solution(object):
        def minCostII(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if not costs: return 0
            n, k = len(costs), len(costs[0])
            for i in xrange(1, n):
                min1 = min(costs[i-1])
                idx = costs[i-1].index(min1)
                min2 = min(costs[i-1][:idx] + costs[i-1][idx+1:])
                for j in xrange(k):
                    if j == idx:
                        costs[i][j] += min2
                    else:
                        costs[i][j] += min1
            return min(costs[-1])
    

    This is a Markov Chain (dp) with k states (color 1, color 2...color k) and n stages, we simply update the costs matrix to keep track of the optimal value for each state at current stage.
    min1 means we paint all other states with the minimum cost, while min2 means we cannot paint consecutive houses with same color so we choose the second lowest cost to add up with.


Log in to reply
 

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