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 背包问题，我们的套路是：
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 背包：
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 可以取无数次，那么正序遍历正好可以满足，如上图。
题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。而本题是要求
恰好装满的。而这两种情况仅仅影响我们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)$
最后贴几个我写过的背包问题，让大家看看历史是多么的相似。
这里内外循环和本题正好是反的，我只是为了"秀技"(好玩)，实际上在这里对答案并不影响。
这里内外循环和本题正好是反的，但是这里必须这么做，否则结果是不对的，具体可以点进去链接看我那个题解
所以这两层循环的位置起的实际作用是什么？ 代表的含义有什么不同？
本质上:
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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 2mo ago