【力扣python】每日抑題——1449. 數位成本和為目标值的最大數字

1449. 數位成本和為目标值的最大數字

此題是昨天的一個困難題，可以用動規來解決，但動規隻能解決一半，還需要進行回退來找到最大的數字；做此題時本人疊代了很多個版本，在此粘貼源碼儲存下

解法目錄

• • • 寫法一
    • 寫法二
    • 寫法三
    • 寫法四
    • 寫法五

寫法一

最原始的版本

###############################################################################################
# 此題有點難度，最大難度在于想到動規隻能解決一半問題，先通過動規拿到最長位數，在通過另一個位置轉換數組
# 來記錄轉移來源，得到最大的數
# 如下是半參考半自己寫，得到的解法，不過逾時了；但同時也是以題知道了一個很好的規律，即
# dp[i][j] = max([dp[i-1][j-per*cost_]+per for per in range(j//cost_+1)]) 和 dp[i][j] = max(dp[i-1][j], dp[i][j-cost_]+1) 是等價的
###########
# 時間複雜度：O(n*target*total)，total為組成的和/目前數的大小，n是cost數組大小，在此題中為9
# 空間複雜度：O(n*target)，動規數組開銷
###############################################################################################
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # 定義dp[i][j]：任意使用前i個cost，得到和為j，所得到的整數的最長位數
        dp = [[0]*(target+1) for _ in range(10)]
        from_ = [[0]*(target+1) for _ in range(10)] # 不能寫成dp = from_ = ... 會指向同一個記憶體
        for i in range(1, target+1):
            dp[0][i] = float("-inf") # 不可能的狀态，設位數為很小
        for i in range(1, 10):
            cost_ = cost[i-1]
            for j in range(target+1):
                if j < cost_: # cost_無法使用
                    dp[i][j] = dp[i-1][j]
                    from_[i][j] = j
                else:
                    max_, max_k = dp[i-1][j], 0
                    for k in range(1, j//cost_+1):
                        if dp[i-1][j-k*cost_]+k >= max_: # 大于等于是為了盡量取更大的數
                            max_ = dp[i-1][j-k*cost_]+k
                            max_k = k
                    dp[i][j] = max_
                    # 其實這裡的寫法和寫成dp[i][j] = max(dp[i-1][j], dp[i][j-cost_]+1)是等價的
                    # dp[i][j] = max([dp[i-1][j-per*cost_]+per for per in range(j//cost_+1)])
                    from_[i][j] = j - cost_ if max_k != 0 else j
        if dp[9][target]<0: # 沒找到
            return "0"
        i, j, res = 9, target, ""
        while(i>0):
            if from_[i][j] == j: # 表示從上一層而來，第i個數沒使用
                i -= 1
            else:
                res += str(i)
                j = from_[i][j]
        return res
           

寫法二

減少一個循環進行優化

## 利用找到的等價性，直接進行優化，減少一個循環
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # 定義dp[i][j]：任意使用前i個cost，得到和為j，所得到的整數的最長位數
        dp = [[0]*(target+1) for _ in range(10)]
        from_ = [[0]*(target+1) for _ in range(10)] # 不能寫成dp = from_ = ... 會指向同一個記憶體
        for i in range(1, target+1):
            dp[0][i] = float("-inf") # 不可能的狀态，設位數為很小
        for i in range(1, 10):
            cost_ = cost[i-1]
            for j in range(target+1):
                if j < cost_: # cost_無法使用
                    dp[i][j], from_[i][j] = dp[i-1][j], j
                else:
                    dp[i][j], from_[i][j] = (dp[i-1][j], j) if dp[i-1][j] > dp[i][j-cost_]+1 else (dp[i][j-cost_]+1, j - cost_)
        if dp[9][target]<0: # 沒找到
            return "0"
        i, j, res = 9, target, ""
        while(i>0):
            if from_[i][j] == j: # 表示從上一層而來，第i個數沒使用
                i -= 1
            else:
                res += str(i)
                j = from_[i][j]
        return res
           

寫法三

把from數組存的内容變成字元串，避免最後還需要進行回退

## 本來按理論分析，可以避免單獨在最後進行倒退找數字，但由于有字元串的操作和存儲，如下代碼雖然精簡，但并沒表現良好，時空消耗均增大
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # 定義dp[i][j]：任意使用前i個cost，得到和為j，所得到的整數的最長位數
        dp = [[0]*(target+1) for _ in range(10)]
        string = [[""]*(target+1) for _ in range(10)]
        for i in range(1, target+1):
            dp[0][i] = float("-inf") # 不可能的狀态，設位數為很小
        for i in range(1, 10):
            cost_ = cost[i-1]
            for j in range(target+1):
                if j < cost_: # cost_無法使用
                    dp[i][j], string[i][j] = dp[i-1][j], string[i-1][j]
                else:
                    dp[i][j], string[i][j] = (dp[i-1][j], string[i-1][j]) if dp[i-1][j] > dp[i][j-cost_]+1 else (dp[i][j-cost_]+1, string[i][j-cost_] + str(i))
        if dp[9][target]<0: # 沒找到
            return "0"
        return string[9][target][::-1]
           

寫法四

再進一步優化空間，使得代碼最精簡化

## 按上面基于string數組的存儲進行優化：優化dp和string空間，優化第二層循環的範圍
## 至此，代碼已經非常精簡，但由于有字元串的操作，時間空間消耗都挺大
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # 定義dp[i][j]：任意使用前i個cost，得到和為j，所得到的整數的最長位數
        dp = [float("-inf")]*(target+1) # 從第0層開始初始化
        dp[0], string = 0, [""]*(target+1) 
        for i, cost_ in enumerate(cost):
            for j in range(cost_, target+1):
                if dp[j] <= dp[j-cost_]+1:
                    dp[j], string[j] = dp[j-cost_]+1, string[j-cost_] + str(i+1)
        return "0" if dp[target]<0 else string[target][::-1]
           

寫法五

放棄字元串的計算和儲存，采用官方的優化方法，直接去掉from數組，僅利用dp的狀态進行回退，大大提升時間空間效率

###############################################################################################
# 放棄使用string的方式來使代碼簡潔，為了提高運作效率，是以基于原來的倒退找數來進行優化
# 看了下官方的from數組優化，直接整個去掉了，比我用string數組來代替還厲害；不過from數組确實沒法改成一維
# 從本質上（定義上）來看，from變成一維不能得到完整的回退資訊，但dp即便隻有最後一層也可以，因為按照定義
# 最後一層dp[j]表示在前9個數中，得到和為j，所用到的整數的最長位數，此時如果對于從大到小的某個cost有
# dp[j] == dp[j - cost] + 1，則說明對于這個cost的數是被使用了的（之是以能這樣，不需要更早一層的dp，
# 是因為當dp[j] ！= dp[j - cost] + 1的時候，一定有dp[j] = dp[j]，即就是上一層的值！）
###########
# 時間複雜度：O(n*target)，其中 n 是數組 cost 的長度
# 空間複雜度：O(target)
###############################################################################################
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # 定義dp[i][j]：任意使用前i個cost，得到和為j，所得到的整數的最長位數
        dp = [float("-inf")]*(target+1) # 不可能的狀态，設位數為很小
        dp[0] = 0 # 從i=0開始初始化，dp[0]表示組成0的時候位數也為0
        for cost_ in cost:
            for j in range(cost_, target+1):
                dp[j] = max(dp[j],dp[j-cost_]+1)
        if dp[target]<0: # 沒找到
            return "0"
        total, res = target, ""
        for i in range(8, -1, -1):
            c = cost[i]
            while total >= c and dp[total] == dp[total - c] + 1:
                res += str(i + 1)
                total -= c
        return res