Form Largest Integer With Digits That Add up to Target LeetCode solution in Python

1
from functools import lru_cache
2

3

4
class Solution:
5
    def largestNumber(self, cost: List[int], target: int) -> str:
6
        @lru_cache(None)
7
        def dfs(t):
8
            if t == 0:
9
                return 0
10
            res = float("-inf")
11
            for digit in range(1, 10):
12
                if t - cost[digit - 1] >= 0:
13
                    res = max(res, dfs(t - cost[digit - 1]) * 10 + digit)
14
            return res
15

16
        res = dfs(target)
17
        return "0" if res == float("-inf") else str(res)