Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/77741/python-solution-with-detailed-explanation

    Paint House https://leetcode.com/problems/paint-house/?tab=Description

    Memoization

    • min_cost[i,j]: minimum cost to paint house i to N-1 such that house i-1 was painted with color j.
    • Base case: return 0 for painting house N (there are only N-1 houses)
    • Initial case: pass -1 as color index for house index -1.
    from collections import defaultdict
    class Solution(object):
        def helper(self, hi, ci, costs, cache):
            if hi == len(costs):
                return 0
            elif hi in cache and ci in cache[hi]:
                return cache[hi][ci]
            else:
                candidates = (i for i in range(3) if i != ci)
                cache[hi][ci] = float('inf')
                for c in candidates:
                    cache[hi][ci] = min(cache[hi][ci], costs[hi][c] + self.helper(hi+1,c, costs,cache))
                return cache[hi][ci]
    
        def minCost(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if costs == []:
                return 0
            cache = defaultdict(dict)
            return  self.helper(0, -1, costs, cache)
    

    Dynamic Programming

    • min_cost[i,j]: minimum cost to paint house 0 to i such that house i was painted with color j.
    • Base case: min_cost[0,j] = costs[0,j]
    from collections import defaultdict
    class Solution(object):
        def minCost(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if costs == []:
                return 0
            N, cache = len(costs), defaultdict(dict)
            K = 3
            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))
    
    • We can reuse the costs table - No need to create new matrix for dp. The dp / costs matrix has house index on rows and colors as columns.
    class Solution(object):
        def minCost(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if costs == []:
                return 0
            N = len(costs)
            for i in range(1, N):
                costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
                costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
                costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
            return min(costs[N-1][0], costs[N-1][1], costs[N-1][2])
    
    

Log in to reply
 

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