Leetcode題解 Python：Form Largest Integer With Digits That Add up to Target

給一串數字[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)