Python O(nk) beat 95% solution with explaination

  • 2
    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
                        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.