1449-数位成本和为目标值的最大数字(Form Largest Integer With Digits That Add up to Target)
发表于：2021-12-03 | 分类： 困难
字数统计: 653 | 阅读时长: 3分钟 | 阅读量：

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

英文原文

Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

  • The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
  • The total cost used must be equal to target.
  • Integer does not have digits 0.

Since the answer may be too large, return it as string.

If there is no way to paint any integer given the condition, return "0".

 

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.

Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.

Example 4:

Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

 

Constraints:

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000

中文题目

给你一个整数数组 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

通过代码

高赞题解

基本分析

根据题意：给定 $1$~$9$ 几个数字，每个数字都有选择成本，求给定费用情况下，凑成的最大数字是多少。

通常我们会如何比较两数大小关系？

首先我们 根据长度进行比较，长度较长数字较大；再者，对于长度相等的数值，从高度往低位进行比较，找到第一位不同，不同位值大的数值较大。

其中规则一的比较优先级要高于规则二。

基于此，我们可以将构造分两步进行。

动态规划 + 贪心

具体的，先考虑「数值长度」问题，每个数字有相应选择成本，所能提供的长度均为 $1$。

问题转换为：有若干物品，求给定费用的前提下，花光所有费用所能选择的最大价值（物品个数）为多少。

每个数字可以被选择多次，属于完全背包模型。

当求得最大「数值长度」后，考虑如何构造答案。

根据规则二，应该尽可能让高位的数值越大越好，因此我们可以从数值 $9$ 开始往数值 $1$ 遍历，如果状态能够由该数值转移而来，则选择该数值。

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(t)$

思考 & 进阶

懂得分两步考虑的话，这道题还是挺简单。虽然是「DP」+「贪心」，但两部分都不难。

其实这道题改改条件/思路，也能衍生出几个版本：

  1. 【思考】如何彻底转化为「01 背包」或者「多重背包」来处理？

    完全背包经过一维优化后时间复杂度为 $O(N * C)$。是否可以在不超过此复杂度的前提下，通过预处理物品将问题转换为另外两种传统背包？

    • 对于「多重背包」答案是可以的。由于给定的最终费用 $t$，我们可以明确算出每个物品最多被选择的次数，可以在 $O(N)$ 的复杂度内预处理额外的 $s[]$ 数组。然后配合「单调队列优化」，做到 $O(N * C)$ 复杂度，整体复杂度不会因此变得更差。
      但转换增加了「预处理」的计算量。为了让转换变成“更有意义”，我们可以在「预处理」时顺便做一个小优化：对于相同成本的数字，只保留数值大的数字。不难证明，当成本相同时，选择更大的数字不会让结果变差。

    • 对于「01 背包」答案是不可以。原因与「多重背包」单纯转换为「01 背包」不会降低复杂度一致。因此本题转换成「01 背包」会使得 $N$ 发生非常数级别的增大。

  2. 【进阶】不再是给定数值 $1$~$9$（取消 $cost$ 数组），转为给定 $nums$ 数组（代表所能选择的数字，不包含 $0$），和相应 $price$ 数组（长度与 $nums$ 一致，代表选择 $nums[i]$ 所消耗的成本为 $price[i]$）。现有做法是否会失效？

    此时 $nums$ 中不再是只有长度为 $1$ 的数值了。但我们「判断数值大小」的两条规则不变。因此「第一步」不需要做出调整，但在进行「第二步」开始前，我们要先对物品进行「自定义规则」的排序，确保「贪心」构造答案过程是正确的。规则与证明都不难请自行思考。

  3. 【进阶】在进阶 $1$ 的前提下，允许 $nums$ 出现 $0$，且确保答案有解（不会返回答案 $0$）,该如何求解？

    增加数值 $0$ 其实只会对最高位数字的决策产生影响。

    我们可以通过预处理转换为「分组 & 树形」背包问题：将 $nums$ 中的非 $0$ 作为一组「主件」（分组背包部分：必须选择一个主件），所有数值作为「附属件」（树形背包部分：能选择若干个，选择附属件必须同时选择主件）。

背包问题（目录）

  1. 01背包 : 背包问题 第一讲

    1. 【练习】01背包 : 背包问题 第二讲（416. 分割等和子集）
    2. 【学习&练习】01背包 : 背包问题 第三讲（416. 分割等和子集）

  2. 完全背包 : 背包问题 第四讲

    1. 【练习】完全背包 : 背包问题 第五讲（279. 完全平方数）

    2. 【练习】完全背包 : 背包问题 第六讲（322. 零钱兑换）

    3. 【练习】完全背包 : 背包问题 第七讲（518. 零钱兑换 II）

    4. 【练习】完全背包 : 背包问题 第 * 讲（1449. 数位成本和为目标值的最大数字）

  3. 多重背包 : 背包问题 第八讲

  1. 多重背包（优化篇）

    1. 多重背包（优化篇）: 背包问题 第九讲
    2. 多重背包（优化篇）: 背包问题 第十讲

  2. 混合背包 : 背包问题 第十一讲

    1. 【练习】混合背包

  3. 分组背包

    1. 【练习】分组背包

  4. 多维背包

    1. 【练习】多维背包 : 背包问题 第 * 讲（474. 一和零）
    2. 【练习】多维背包 : 背包问题 第 * 讲（879. 盈利计划）

  1. 树形背包

    1. 【练习】树形背包

  2. 背包求方案数

    1. 【练习】背包求方案数 : 背包问题 第 * 讲（494. 目标和）
    2. 【练习】背包求方案数 : 背包问题 第 * 讲（879. 盈利计划）

  1. 背包求具体方案

    1. 【练习】背包求具体方案 : 背包问题 第 * 讲（1049. 最后一块石头的重量 II）
    2. 【练习】背包求具体方案 : 背包问题 第 * 讲（1449. 数位成本和为目标值的最大数字）

  1. 泛化背包

    1. 【练习】泛化背包

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数 提交次数 AC比率
16691 26599 62.8%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
动态规划 数组
上一篇:
1448-统计二叉树中好节点的数目(Count Good Nodes in Binary Tree)
下一篇:
1436-旅行终点站(Destination City)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo