Python 3   ||   9 lines,  w/ recursion and cache   ||   T/S: 98% / 100%
We determine the optimum choice of toppings for each base using dp, a recursive, cached function. \n\n\nclass Solution:\n    def closestCost(self, baseCosts: Li
We determine the optimum choice of toppings for each base using `dp`, a recursive, cached function. \n\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], \n                          toppingCosts: List[int], \n                          target: int) -> int:\n        \n        @lru_cache(None)\n        def dp(idx, cost):\n            if idx == len(toppingCosts) or cost > target:\n                return cost\n\n            c = toppingCosts[idx]\n            ans = (dp(idx+1,cost), dfs(idx+1,cost+c), dfs(idx+1,cost+2*c))\n            return min(ans,key = lambda x: (abs(x - target), x))\n  \n        ans = [dp(0, cost) for cost in baseCosts]\n\n        return min(ans,key = lambda x: (abs(x - target), x))\n```\n[https://leetcode.com/problems/closest-dessert-cost/submissions/697551622/](https://leetcode.com/problems/closest-dessert-cost/submissions/697551622/)\n\nI could be wrong, but I think that time complexity is *O*(*M* 3^*N*) and space complexity is *O*(*N*), in which *N* ~ `len(toppingCosts)` and *M* ~ `len(baseCosts)`.
['Python', 'Python3']