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

# 1449. 数位成本和为目标值的最大数字 # 题目地址（1449. 数位成本和为目标值的最大数字） <https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/> ## 题目描述 ``` <pre class="calibre18">``` 给你一个整数数组 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 背包问题，我们的套路是： ``` <pre class="calibre18">``` for i in 0 to N: for j in 1 to V + 1: dp[j] = max(dp[j], dp[j - cost[i]) ``` ``` 而一般我们为了处理边界问题，我们一般会这么写代码： ``` <pre class="calibre18">``` 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 值 ### 完全背包问题回到问题，我们这是完全背包问题: ``` <pre class="calibre18">``` 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 背包： ``` <pre class="calibre18">``` 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 只能取一次嘛。那么如果我们不降序遍历会怎么样呢？ ![](https://img.kancloud.cn/81/f8/81f8664f87d2eeed79f4e2658a480784_1114x594.jpg) 如图橙色部分表示已经遍历的部分，而让我们去用\[j - cost\[i - 1\]\] 往前面回溯的时候，实际上回溯的是 dp\[i\]j - cost\[i - 1\]\]，而不是 dp\[i - 1\]j - cost\[i - 1\]\]。如果是降序就可以了，如图： ![](https://img.kancloud.cn/82/a6/82a62cef214772a2076ae5f0c1240f09_1088x552.jpg) 这个明白的话，我们继续思考为什么完全背包就要不降序了呢？我们还是像上面一样写出二维的代码： ``` <pre class="calibre18">``` 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 从后往前遍历，因为后面表示的数字大。 ## 代码 ``` <pre class="calibre18">``` 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))O(target)) - 空间复杂度：O(target)O(target)O(target) ## 扩展最后贴几个我写过的背包问题，让大家看看历史是多么的相似。 ![](https://img.kancloud.cn/c2/f5/c2f52308a45a8b8e961bbdef8359c757_1586x830.jpg)（[322. 硬币找零(完全背包问题)](https://github.com/azl397985856/leetcode/blob/master/problems/322.coin-change.md)） > 这里内外循环和本题正好是反的，我只是为了"秀技"(好玩)，实际上在这里对答案并不影响。 ![](https://img.kancloud.cn/9b/eb/9beb32f6a1edd77bf5776b2cecc0404d_1586x508.jpg)（[518. 零钱兑换 II](https://github.com/azl397985856/leetcode/blob/master/problems/518.coin-change-2.md)） > 这里内外循环和本题正好是反的，但是这里必须这么做，否则结果是不对的，具体可以点进去链接看我那个题解所以这两层循环的位置起的实际作用是什么？代表的含义有什么不同？本质上: ``` <pre class="calibre18">``` for i in 1 to N + 1: for j in V to 0: ... ``` ``` 这种情况选择物品 1 和物品 3（随便举的例子），是一种方式。选择物品 3 个物品 1（注意是有顺序的）是同一种方式。 **原因在于你是固定物品，去扫描容量**。而： ``` <pre class="calibre18">``` 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg) ![](https://img.kancloud.cn/7b/b1/7bb115b82aa493e2d2a88f71d5201779_1190x680.jpg)