lucifer

这是一道难度 Hard 的经典背包问题,属于完全背包问题,来看看背包问题的套路吧~

题目地址(1449. 数位成本和为目标值的最大数字)

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

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
给你一个整数数组 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 背包问题,我们的套路是:

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

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

1
2
3
4
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 值

完全背包问题

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

1
2
3
4
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 背包:

1
2
3
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]]。

如果是降序就可以了,如图:

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

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

1
2
3
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 从后往前遍历,因为后面表示的数字大。

代码

1
2
3
4
5
6
7
8
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

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

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

本质上:

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

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

而:

1
2
3
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 。 目前已经 30K star 啦。

大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解


 评论


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 。
载入天数...载入时分秒...