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

给你一个整数数组 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

动态规划 困难 每日一题

题解

代码

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [[float("-inf")] * (target + 1) for _ in range(10)]
        where = [[0] * (target + 1) for _ in range(10)]
        dp[0][0] = 0

        for i, c in enumerate(cost):
            for j in range(target + 1):
                if j < c:
                    dp[i + 1][j] = dp[i][j]
                    where[i + 1][j] = j
                else:
                    if dp[i][j] > dp[i + 1][j - c] + 1:
                        dp[i + 1][j] = dp[i][j]
                        where[i + 1][j] = j
                    else:
                        dp[i + 1][j] = dp[i + 1][j - c] + 1
                        where[i + 1][j] = j - c
        
        if dp[9][target] < 0:
            return "0"
        
        ans = list()
        i, j = 9, target
        while i > 0:
            if j == where[i][j]:
                i -= 1
            else:
                ans.append(str(i))
                j = where[i][j]
        
        return "".join(ans)

或者

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        # discard: cost相同的数字取最大的，对其他的标记一下不再使用
        dp, discard = [0] * (target + 1),  [False] * 9
        for i in range(8, -1, -1):
            if cost[i] <= target and dp[cost[i]] == 0:
                dp[cost[i]] = i + 1
            else:
                discard[i] = True

        # 遍历digit时使用倒序，这样数字越来越小，挨个往后加即可
        for i in (i_ for i_ in range(8, -1, -1) if not discard[i_]):
            for total in range(cost[i], target + 1):
                if dp[total - cost[i]] != 0:
                    dp[total] = max(dp[total], dp[total - cost[i]] * 10 + i + 1)
        return str(dp[target])