数位成本和为目标值的最大数字

难度: Hard

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"

提示：

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

Submission

运行时间: 86 ms

内存: 28.3 MB

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        res = Counter(cost)
        dp = [""] + ["0"]*target
        for i in range(1, 10):
            x = cost[i-1]
            for j in range(target-x+1):
                if dp[j] == "0" or len(dp[j])+1 < len(dp[j+x]):
                    continue
                o = str(i) + dp[j]
                if len(o) > len(dp[j+x]) or len(o) == len(dp[j+x]) and dp[j+x] < o:
                    dp[j+x] = o
        # print(dp)
        return dp[target]

Explain

这个题解使用了动态规划的方法来求解问题。dp数组的长度是target+1，其中dp[j]存储的是当成本为j时能构成的最大数字。初始化dp[0]为一个空字符串（表示成本为0时不需要任何数字），而其他dp[j]（1 <= j <= target）则初始化为'0'（表示无法由给定的成本构造任何数字）。遍历每个数字i从1到9，对于每个数字，检查它的成本x是否能够被添加到当前成本j形成新的成本j+x，并更新dp[j+x]。如果在添加数字i后形成的字符串比之前存储在dp[j+x]中的字符串要大（或者长度更长），则更新dp[j+x]。最后返回dp[target]，如果它仍然是'0'，则表示无法凑出目标成本，否则返回构成的最大数字字符串。

时间复杂度: O(target)

空间复杂度: O(target)

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [''] + ['0']*target # 初始化dp数组，dp[0]为空字符串，其他为'0'
        for i in range(1, 10): # 遍历每个数字i从1到9
            x = cost[i-1] # 获取数字i的成本
            for j in range(target-x+1): # 遍历所有可能的成本j
                if dp[j] == '0' or len(dp[j])+1 < len(dp[j+x]): # 如果当前成本无法构成数字或者不能构成更大的数字，跳过
                    continue
                o = str(i) + dp[j] # 构成新的数字字符串
                if len(o) > len(dp[j+x]) or (len(o) == len(dp[j+x]) and dp[j+x] < o): # 如果新字符串更优，则更新dp[j+x]
                    dp[j+x] = o
        return dp[target] # 返回能用成本target构成的最大数字字符串，如果是'0'则返回'0'

Explore

在动态规划的实现中，确保dp数组总是存储最大数字字符串的关键在于每次更新dp[j+x]时，都会比较现有的字符串和新构成的字符串。在更新过程中，如果新生成的字符串（由当前考虑的数字i拼接在dp[j]的前面形成的字符串）的长度更长，或者长度相同但字典序更大，则更新dp[j+x]。这样的对比和更新保证了dp[j+x]总是存储了可能的最大数字字符串。

在这个问题的上下文中，dp[0]初始化为空字符串是因为成本为0时不需使用任何数字，即最大数字是一个空的表示（没有数字，代表成本0的情况）。对于dp[j]（1 <= j <= target），它们初始化为'0'代表在当前成本下无法构成任何有效的数字。这是一个标记值，用来区分那些还没有找到有效解的成本值。这种初始化方法帮助算法在开始时有一个明确的标记，以区分已解决和未解决的成本值。

如果dp[j]是'0'，这意味着对于当前成本j，我们还没有找到任何有效的数字组合，因此无法通过添加任何数字来形成有效的更高成本的数字组合。另外，如果dp[j]的长度加一仍然小于dp[j+x]的长度，这意味着即使添加了一个数字，构成的新数字字符串仍然不会比已存储在dp[j+x]中的字符串更优（更长或字面值更大）。因此，在这两种情况下更新是无意义的，所以代码会跳过这些更新以节省计算资源和时间。

这个条件是用来检查通过当前数字i和成本j形成的新数字字符串是否具有潜力成为dp[j+x]中的最大字符串。如果'len(dp[j])+1 < len(dp[j+x])'，则即使添加了数字i，通过成本j形成的新字符串长度仍然小于或等于当前存储在dp[j+x]中的字符串长度，表明新字符串在长度上不优于已有字符串。因此，只有当新形成的字符串长度大于或等于dp[j+x]时，才有更新dp[j+x]的必要。这个条件帮助避免不必要的更新，优化算法效率。