1449. Form Largest Integer With Digits That Add up to Target

https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        self.cache = dict()
        def dp(target):
            if target < 0:
                return "0"
            if target == 0:
                return ""
            if target in self.cache:
                return self.cache[target]
            res = ""
            for i in range(9,0,-1):
                curr = dp(target - cost[i-1])
                if curr == "0":
                    continue
                curr = str(i) + curr
                if len(curr) > len(res):
                    res = curr
            if res == "":
                self.cache[target]="0"
                return "0"
            self.cache[target] = res
            return res
        return dp(target)