跳至主要內容

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

ITCharge大约 3 分钟

1449. 数位成本和为目标值的最大数字open in new window

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

题目链接

题目大意

描述:给定一个整数数组 costcost 和一个整数 targettarget。现在从 "" 开始,不断通过以下规则得到一个新的整数:

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

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

说明

  • 由于答案可能会很大,请你以字符串形式返回。
  • 如果按照上述要求无法得到任何整数,请你返回 "0"
  • cost.length==9cost.length == 9
  • 1cost[i]50001 \le cost[i] \le 5000
  • 1target50001 \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

解题思路

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

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

思路 1:动态规划

1. 划分阶段

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

2. 定义状态

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

3. 状态转移方程

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

4. 初始条件
  1. 只有载重上限为 00 的背包,在不放入物品时,能够恰好装满背包(有合法解),此时背包所含物品的最大价值为空字符串,即 dp[0] = ""
  2. 其他载重上限下的背包,在放入物品的时,都不能恰好装满背包(都没有合法解),此时背包所含物品的最大价值属于未定义状态,值为自定义字符 "#",即 ,dp[w] = "#"0wtarget0 \le w \le target
5. 最终结果

根据我们之前定义的状态,dp[w]dp[w] 表示为:将物品装入一个最多能装重量为 ww 的背包中,恰好装满背包的情况下,能装入背包的最大价值总和。 所以最终结果为 dp[target]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×target)O(n \times target),其中 nn 为数组 costcost 的元素个数,targettarget 为所给整数。
  • 空间复杂度O(target)O(target)