給一串數字[1-9]的花費 cost，跟 總花費 target，回傳總花費相等的最大可能數字。
這題是DP，我本來感覺沒很難，結果敗在這裡 QQ 。考驗對DP與遞迴函數的熟練度。(我用了一些時間才精簡到可行)
對於規劃，函數要使用 t 也就是剩餘的花費，在同一個 t 之下，結果只會有一個最大值。
(我一開始用三個、二個都會超時，睡起再改成一個)
於是要朝著 dfs(t) 的方向前進。
在[1-9]花費有可能一樣的，為了加速，二者花費相等，只要保留較大的數字，結果也只會用到最大的數字。
如果 t == 0 做中止條件，那麼就無法知道是哪個數字讓其歸零。
得用 t – each_cost == 0，這樣就可以知道哪個數字了。
回傳值是最大的數字，若 t – each_cost > 0，那麼應該用 dfs(t – each_cost)去找出後面的最大數字，
並與 each_cost 代表的數字結合。
而 each_cost 有數種，同個 t 之下也有不同的組合，所以用 max() 去選出最大的數字，才能符合設計。
Python
class Solution:
def largestNumber(self, cost, target) -> str:
from functools import lru_cache
cost_dict = dict()
for i, c in enumerate(cost):
cost_dict[c] = str(i+1)
sorted_dk = sorted(cost_dict.keys())
@lru_cache(None)
def dfs(t):
ans = 0
for c in sorted_dk:
if t - c == 0:
ans = max(ans, int(cost_dict[c]))
elif t - c < 0:
break
else:
result = dfs(t - c)
if result != "0":
ans = max(ans, int(cost_dict[c] + result))
return str(ans)
return dfs(target)