Python DFS solution similar to combination sum, ETL, help wanted


  • 0
    B

    At first glance, this question reminds me of a typical dfs/backtrack question, such as combination/permutation/combination sum. My code can pass small set test, but it failed for large data set. Can anyone help me optimize it? Thanks

    class Solution(object):
        def minCost(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if not costs:
                return 0
                
            self.result = sys.maxint
            # start with R/G/B
            self.dfs(0, 0, costs[0][0], costs)
            self.dfs(0, 1, costs[0][1], costs)
            self.dfs(0, 2, costs[0][2], costs)
            return self.result
            
        def dfs(self, depth, color, currsum, costs):
            if depth == len(costs)-1:
                self.result = min(self.result, currsum)
                return
            for c in (set([0,1,2]) - set([color])):
                self.dfs(depth+1, c, currsum+costs[depth+1][c], costs)
    

Log in to reply
 

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