638.md

class Solution:
    def shoppingOffers(self, price, special, needs):
        """
        :type price: List[int]
        :type special: List[List[int]]
        :type needs: List[int]
        :rtype: int
        """
        dp = dict()
        def solve(tup):
            if tup in dp: 
                return dp[tup]
            dp[tup] = sum(t * p for t, p in zip(tup, price))
            for sp in special:
                ntup = tuple(t - s for t, s in zip(tup, sp))
                if min(ntup) < 0:
                    continue
                dp[tup] = min(dp[tup], solve(ntup) + sp[-1])
            return dp[tup]
        return solve(tuple(needs))

动态规划 深度搜索