A python DP solution


  • 0
    F

    It's a DP solution, but cost much more time than DFS solution. The hash operation took a lot of time

    from itertools import product, izip
    class Solution(object):
        def shoppingOffers(self, price, special, needs):
            """
            :type price: List[int]
            :type special: List[List[int]]
            :type needs: List[int]
            :rtype: int
            """
            mul = lambda z: reduce(lambda x,y: x*(y+1), z, 1) if z else 1
            sub = lambda m,n: map(lambda x,y: x-y, m, n)
    
            needSpace = mul(needs)
            
            map_index_group_2_index = dict(zip(product(*(xrange(x+1) for x in needs)), range(needSpace)))
            self.map_index_group_2_index = map_index_group_2_index
                    
            price_list = []
            for i in range(len(price)):
                l = [0] * len(price)
                l[i] = 1
                l.append(price[i])
                price_list.append(l)
                
            dp = [1000000000]*needSpace
            dp[0] = 0
            for ticket in price_list + special:
                buy_group = ticket[:-1]
                buy_price = ticket[-1]
                if not needs >= buy_group: continue
                for need_group, group in izip(product(*(range(x, y+1) for x,y in zip(buy_group, needs))), product(*(range(x+1) for x in sub(needs, buy_group)))):
                    index = self.map_index_group_2_index[group]
                    if not dp[index] == 1000000000:
                        i = self.map_index_group_2_index[need_group]
                        dp[i] = min(dp[index] + buy_price, dp[i])
            return dp[needSpace-1]
    

Log in to reply
 

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