Python memorization


  • 0
    X
    class Solution(object):
        def shoppingOffers(self, price, special, needs):
            """
            :type price: List[int]
            :type special: List[List[int]]
            :type needs: List[int]
            :rtype: int
            """
            special = list( real_special(price, special, needs) )
            needs = tuple(needs)
            cache = {}
            def dfs(needs):
                ret = cache.get(needs)
                if ret:
                    return ret
                vals = [ tot + dfs( tuple(need-cnt for need, cnt in zip(needs, cnts)) )
                            for cnts, tot in special
                                if _le(cnts, needs) ]
                if vals:
                    ret = min(vals)
                else:
                    ret = sum(v*cnt for v, cnt in zip(price, needs))
                cache[needs] = ret
                return ret
            return dfs(needs)
    
    def _le(vectl, vectr):
        return all(l <= r for l, r in zip(vectl, vectr))
        
    def real_special(price, special, needs):
        for offer in special:
            cnts, tot = offer[:-1], offer[-1]
            if tot >= sum(v * cnt for v, cnt in zip(price, cnts)):
                continue
            if _le(cnts, needs):
                yield tuple(cnts), tot
    
        
        
    

Log in to reply
 

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