题目描述
这是 LeetCode 上的 1449. 数位成本和为目标值的最大数字 ,难度为 困难。
Tag : 「完全背包」、「背包问题」、「动态规划」
给你一个整数数组 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 。 "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 。 复制代码
示例 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
基本分析
根据题意:给定 11~99 几个数字,每个数字都有选择成本,求给定费用情况下,凑成的最大数字是多少。
通常我们会如何比较两数大小关系?
首先我们 根据长度进行比较,长度较长数字较大;再者,对于长度相等的数值,从高度往低位进行比较,找到第一位不同,不同位值大的数值较大。
其中规则一的比较优先级要高于规则二。
基于此,我们可以将构造分两步进行。
动态规划 + 贪心
具体的,先考虑「数值长度」问题,每个数字有相应选择成本,所能提供的长度均为 11。
问题转换为:有若干物品,求给定费用的前提下,花光所有费用所能选择的最大价值(物品个数)为多少。
每个数字可以被选择多次,属于完全背包模型。
当求得最大「数值长度」后,考虑如何构造答案。
根据规则二,应该尽可能让高位的数值越大越好,因此我们可以从数值 99 开始往数值 11 遍历,如果状态能够由该数值转移而来,则选择该数值。
PS. 写了几天两维版本了,大家应该都掌握了叭,今天赶着出门,直接写一维。
代码:
class Solution { public String largestNumber(int[] cost, int t) { int[] f = new int[t + 1]; Arrays.fill(f, Integer.MIN_VALUE); f[0] = 0; for (int i = 1; i <= 9; i++) { int u = cost[i - 1]; for (int j = u; j <= t; j++) { f[j] = Math.max(f[j], f[j - u] + 1); } } if (f[t] < 0) return "0"; String ans = ""; for (int i = 9, j = t; i >= 1; i--) { int u = cost[i - 1]; while (j >= u && f[j] == f[j - u] + 1) { ans += String.valueOf(i); j -= u; } } return ans; } } 复制代码
- 时间复杂度:O(n * t)O(n∗t)
- 空间复杂度:O(t)O(t)
思考 & 进阶
懂得分两步考虑的话,这道题还是挺简单。虽然是「DP」+「贪心」,但两部分都不难。
其实这道题改改条件/思路,也能衍生出几个版本:
- 【思考】如何彻底转化为「01 背包」或者「多重背包」来处理?完全背包经过一维优化后时间复杂度为O(N * C)O(N∗C)。是否可以在不超过此复杂度的前提下,通过预处理物品将问题转换为另外两种传统背包?
- 对于「多重背包」答案是可以的。由于给定的最终费用 tt,我们可以明确算出每个物品最多被选择的次数,可以在 O(N)O(N) 的复杂度内预处理额外的 s[]s[] 数组。然后配合「单调队列优化」,做到 O(N * C)O(N∗C) 复杂度,整体复杂度不会因此变得更差。 但转换增加了「预处理」的计算量。为了让转换变成“更有意义”,我们可以在「预处理」时顺便做一个小优化:对于相同成本的数字,只保留数值大的数字。不难证明,当成本相同时,选择更大的数字不会让结果变差。
- 对于「01 背包」答案是不可以。原因与「多重背包」单纯转换为「01 背包」不会降低复杂度一致。因此本题转换成「01 背包」会使得 NN 发生非常数级别的增大。
- 【进阶】不再是给定数值 11~99(取消 costcost 数组),转为给定 numsnums 数组(代表所能选择的数字,不包含 00),和相应 priceprice 数组(长度与 numsnums 一致,代表选择 nums[i]nums[i] 所消耗的成本为 price[i]price[i])。现有做法是否会失效?
此时 numsnums 中不再是只有长度为 11 的数值了。但我们「判断数值大小」的两条规则不变。因此「第一步」不需要做出调整,但在进行「第二步」开始前,我们要先对物品进行「自定义规则」的排序,确保「贪心」构造答案过程是正确的。规则与证明都不难请自行思考。 - 【进阶】在进阶 11 的前提下,允许 numsnums 出现 00,且确保答案有解(不会返回答案 00),该如何求解?
增加数值 00 其实只会对最高位数字的决策产生影响。
我们可以通过预处理转换为「分组 & 树形」背包问题:将 numsnums 中的非 00 作为一组「主件」(分组背包部分:必须选择一个主件),所有数值作为「附属件」(树形背包部分:能选择若干个,选择附属件必须同时选择主件)。
背包问题(目录)
- 01背包 :背包问题 第一讲
- 【练习】01背包 : 背包问题 第二讲(416. 分割等和子集)
- 【学习&练习】01背包 : 背包问题 第三讲(416. 分割等和子集)
- 完全背包 :背包问题 第四讲
- 【练习】完全背包 : 背包问题 第五讲(279. 完全平方数)
- 【练习】完全背包 : 背包问题 第六讲(322. 零钱兑换)
- 【练习】完全背包 : 背包问题 第七讲(518. 零钱兑换 II)
- 【练习】完全背包 : 背包问题 第 * 讲(1449. 数位成本和为目标值的最大数字)
- 多重背包 : 背包问题 第八讲
- 多重背包(优化篇)
- 混合背包
- 【练习】混合背包
- 分组背包
- 【练习】分组背包
- 多维背包
- 【练习】多维背包 : 背包问题 第 * 讲(474. 一和零)
- 【练习】多维背包 : 背包问题 第 * 讲(879. 盈利计划)
- 树形背包
- 【练习】树形背包
- 背包求方案数
- 【练习】背包求方案数 : 背包问题 第 * 讲(494. 目标和)
- 【练习】背包求方案数 : 背包问题 第 * 讲(879. 盈利计划)
- 背包求具体方案
- 【练习】背包求具体方案 : 背包问题 第 * 讲(1049. 最后一块石头的重量 II)
- 【练习】背包求具体方案 : 背包问题 第 * 讲(1449. 数位成本和为目标值的最大数字)
- 泛化背包
- 【练习】泛化背包
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1449
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。