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

• 标签：数组、动态规划
• 难度：困难

题目链接

• 1449. 数位成本和为目标值的最大数字 - 力扣

题目大意

描述：给定一个整数数组 $cost$ 和一个整数 $target$。现在从 "" 开始，不断通过以下规则得到一个新的整数：

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

要求：找到按照上述规则可以得到的最大整数。

说明：

• 由于答案可能会很大，请你以字符串形式返回。
• 如果按照上述要求无法得到任何整数，请你返回 "0"。
• $cost.length == 9$。
• $1 \le cost[i] \le 5000$。
• $1 \le target \le 5000$。

示例：

• 示例 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。
 数字     成本
  1  ->   7
  2  ->   6
  3  ->   5
  4  ->   5
  5  ->   5
  6  ->   6
  7  ->   8
  8  ->   7
  9  ->   8

解题思路

把每个数位（$1 \sim 9$）看做是一件物品，$cost[i]$ 看做是物品的重量，一共有无数件物品可以使用，$target$ 看做是背包的载重上限，得到的最大整数可以看做是背包的最大价值。那么问题就变为了「完全背包问题」中的「恰好装满背包的最大价值问题」。

因为答案可能会很大，要求以字符串形式返回。这里我们可以直接令 $dp[w]$ 为字符串形式，然后定义一个 def maxInt(a, b): 方法用于判断两个字符串代表的数字大小。

思路 1：动态规划

1. 划分阶段

按照背包载重上限进行阶段划分。

2. 定义状态

定义状态 $dp[w]$ 表示为：将物品装入一个最多能装重量为 $w$ 的背包中，恰好装满背包的情况下，能装入背包的最大整数。

3. 状态转移方程

$dp[w] = maxInt(dp[w], str(i) + dp[w - cost[i - 1]])$

4. 初始条件

1. 只有载重上限为 $0$ 的背包，在不放入物品时，能够恰好装满背包（有合法解），此时背包所含物品的最大价值为空字符串，即 dp[0] = ""。
2. 其他载重上限下的背包，在放入物品的时，都不能恰好装满背包（都没有合法解），此时背包所含物品的最大价值属于未定义状态，值为自定义字符 "#"，即 ，dp[w] = "#"，$0 \le w \le target$。

5. 最终结果

根据我们之前定义的状态，$dp[w]$ 表示为：将物品装入一个最多能装重量为 $w$ 的背包中，恰好装满背包的情况下，能装入背包的最大价值总和。 所以最终结果为 $dp[target]$。

思路 1：代码

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        def maxInt(a, b):
            if len(a) == len(b):
                return max(a, b)
            if len(a) > len(b):
                return a
            return b

        size = len(cost)
        dp = ["#" for _ in range(target + 1)]
        dp[0] = ""

        for i in range(1, size + 1):
            for w in range(cost[i - 1], target + 1):
                if dp[w - cost[i - 1]] != "#":
                    dp[w] = maxInt(dp[w], str(i) + dp[w - cost[i - 1]])
        if dp[target] == "#":
            return "0"
        return dp[target]

思路 1：复杂度分析

• 时间复杂度：$O(n \times target)$，其中 $n$ 为数组 $cost$ 的元素个数，$target$ 为所给整数。
• 空间复杂度：$O(target)$。