Python solution with detailed explanation


  • 0
    G

    Solution

    1. Refer to paint-house 1 problem to understand the recursion well.
    2. costs[i,j] means what is the minimum cost of painting houses from index 0 to i such that ith house is painted with color j. If ith house is painted with color 0, then the i-1 th house must be color other than j.
    3. The solution is exactly similar to Paint House 1. We can reuse cost array for our DP array. In that solution, we need to always extract the minimum cost from the previos row with j index not the same as current j index.
    4. The similar solution to Paint House 1 is O(N * K^2).
    from collections import defaultdict
    class Solution(object):
        def minCostII(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if costs == []:
                return 0
            N, K, cache = len(costs), len(costs[0]), defaultdict(dict)
            for k in range(K):
                cache[0][k] = costs[0][k]
            for i in range(1,N):
                for j in range(K):
                    cache[i][j], candidates = float('inf'), (k for k in range(K) if j != k)
                    for c in candidates:
                        cache[i][j] = min(cache[i][j], cache[i-1][c]+costs[i][j])
            return min(cache[N-1][k] for k in range(K))
    

    Optimized Solution

    • The optimized solution is O(N * K). To get there, we use a nice little trick.
    • The recursion is: costs[i][j] = costs[i][j] + min_prev_cost. Think what are the possible values of min_prev_cost. Either it is the minimum value in previous row if the minimum value in the previous row doesnt have same color index as j, or it is the second minimum value.
    • So we just need to maintain two minimum values from previous row.
    • The general algorithm to maintain that is to first store k values. Then for k+1 value, evict the maximum. But for 2 values, we can do it by two variables. Imagine m1 and m2 as the two minimum values. If the cost is less than m1, then simply set m1 to c and make m2 equal to m1. If cost is more than m1 but less than m2, then make m2 equal to c.
    class Solution(object):
        def minCostII(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if costs == []:
                return 0
                
            N, K = len(costs), len(costs[0])
            m1, m2 = float('inf'), float('inf')
            m1_index = -1
            
            for j in range(K):
                if costs[0][j] < m1:
                    m2, m1, m1_index = m1, costs[0][j], j
                elif costs[0][j] < m2:
                    m2 = costs[0][j]
                    
            for i in range(1, N):
                m1_, m2_ = float('inf'), float('inf')
                m1_index_ = -1
                for j in range(K):
                    min_prev_cost = m1 if j != m1_index else m2
                    costs[i][j] = costs[i][j] + min_prev_cost
                    if costs[i][j] < m1_:
                        m2_, m1_, m1_index_ = m1_, costs[i][j], j
                    elif costs[i][j] < m2_:
                        m2_ = costs[i][j]
                m1, m2 = m1_, m2_
                m1_index = m1_index_
                
            return min(costs[N-1])    
    

Log in to reply
 

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