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

https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

题目描述

给你一个整数数组 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 。 "997" 也是满足要求的数字，但 "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

前置知识

• 数组

• 动态规划

• 背包问题

公司

• 暂无

思路

由于数组可以重复选择，因此这是一个完全背包问题。

01 背包

对于 01 背包问题，我们的套路是：

for i in 0 to N:
    for j in 1 to V + 1:
        dp[j] = max(dp[j], dp[j - cost[i])

而一般我们为了处理边界问题，我们一般会这么写代码：

for i in 1 to N + 1:
    # 这里是倒序的，原因在于这里是01背包。
    for j in V to 0:
        dp[j] = max(dp[j], dp[j - cost[i - 1])

其中 dp[j] 表示只能选择前 i 个物品，背包容量为 j 的情况下，能够获得的最大价值。

dp[j] 不是没 i 么？ 其实我这里 i 指的是 dp[j]当前所处的循环中的 i 值

完全背包问题

回到问题，我们这是完全背包问题:

for i in 1 to N + 1:
    # 这里不是倒序，原因是我们这里是完全背包问题
    for j in 1 to V + 1:
        dp[j] = max(dp[j], dp[j - cost[i - 1])

为什么 01 背包需要倒序，而完全背包则不可以

实际上，这是一个骚操作，我来详细给你讲一下。

其实要回答这个问题，我要先将 01 背包和完全背包退化二维的情况。

对于 01 背包：

for i in 1 to N + 1:
    for j in V to 0:
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i - 1])

注意等号左边是 i，右边是 i - 1，这很好理解，因为 i 只能取一次嘛。

那么如果我们不降序遍历会怎么样呢？

如图橙色部分表示已经遍历的部分，而让我们去用[j - cost[i - 1]] 往前面回溯的时候，实际上回溯的是 dp[i]j - cost[i - 1]]，而不是 dp[i - 1]j - cost[i - 1]]。

如果是降序就可以了，如图：

这个明白的话，我们继续思考为什么完全背包就要不降序了呢？

我们还是像上面一样写出二维的代码：

for i in 1 to N + 1:
   for j in 1 to V + 1:
       dp[i][j] = max(dp[i - 1][j], dp[i][j - cost[i - 1])

由于 i 可以取无数次，那么正序遍历正好可以满足，如上图。

恰好装满 VS 可以不装满

题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。而本题是要求恰好装满的。而这两种情况仅仅影响我们dp数组初始化。

• 恰好装满。只需要初始化 dp[0] 为 0， 其他初始化为负数即可。

• 可以不装满。 只需要全部初始化为 0，即可，

原因很简单，我多次强调过 dp 数组本质上是记录了一个个自问题。 dp[0]是一个子问题，dp[1]是一个子问题。。。

有了上面的知识就不难理解了。 初始化的时候，我们还没有进行任何选择，那么也就是说 dp[0] = 0，因为我们可以通过什么都不选达到最大值 0。而 dp[1],dp[2]...则在当前什么都不选的情况下无法达成，也就是无解，因为为了区分，我们可以用负数来表示，当然你可以用任何可以区分的东西表示，比如 None。

回到本题

而这道题和普通的完全背包不一样，这个是选择一个组成的最大数。由小学数学知识一个数字的全排列中，按照数字降序排列是最大的，我这里用了一个骚操作，那就是 cost 从后往前遍历，因为后面表示的数字大。

代码

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [float('-inf')] * target
        for i in range(9, 0, -1):
            for j in range(1, target+1):
                if j >= cost[i - 1]:
                    dp[j] = max(dp[j], (dp[j-cost[i - 1]] * 10) + i)
        return str(dp[target]) if dp[target] > 0 else '0'

复杂度分析

• 时间复杂度：$O(target))$

• 空间复杂度：$O(target)$

扩展

最后贴几个我写过的背包问题，让大家看看历史是多么的相似。

（322. 硬币找零(完全背包问题)）

这里内外循环和本题正好是反的，我只是为了"秀技"(好玩)，实际上在这里对答案并不影响。

（518. 零钱兑换 II）

这里内外循环和本题正好是反的，但是这里必须这么做，否则结果是不对的，具体可以点进去链接看我那个题解

所以这两层循环的位置起的实际作用是什么？ 代表的含义有什么不同？

本质上:

for i in 1 to N + 1:
    for j in V to 0:
        ...

这种情况选择物品 1 和物品 3（随便举的例子），是一种方式。选择物品 3 个物品 1（注意是有顺序的）是同一种方式。 原因在于你是固定物品，去扫描容量。

而：

for j in V to 0:
    for i in 1 to N + 1:
        ...

这种情况选择物品 1 和物品 3（随便举的例子），是一种方式。选择物品 3 个物品 1（注意是有顺序的）也是一种方式。原因在于你是固定容量，去扫描物品。

因此总的来说，如果你认为[1,3]和[3,1]是一种，那么就用方法 1 的遍历，否则用方法 2。

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。