Trace
6.12 每日一题
传送门：https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
Problem
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：
- 给当前结果添加一个数位（
i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
- 总成本必须恰好等于
target 。
- 添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 “0” 。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入：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：
1
2
3
| 输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。
|
示例 3：
1
2
3
| 输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。
|
示例 4：
1
2
| 输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"
|
数据范围：
1
2
3
| cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000
|
思路
要求输出最大的整数：首先根据长度比较，长度较长的数较大；其次数字长度相同，从高位到地位依次比较。
dp+贪心输出方案
$f[i][j]$：从前$i$个数中选，每个数可以取无数次，代价（类比完全背包中的体积）为$j$的取法中，取得的物品数（数字位数）最多是多少。
输出方案时按从$9-1$的次序输出，参考完全背包中输出方案的写法。
https://zhuanlan.zhihu.com/p/139368825
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
| class Solution {
public:
int f[10][5001];
string largestNumber(vector<int>& cost, int target) {
for(int i=0;i<10;i++){
for(int j=0;j<=target;j++){
f[i][j]=-0x3f3f3f3f;
}
}
f[0][0]=0;
for(int i=1;i<10;i++){
for(int j=0;j<=target;j++){
f[i][j]=f[i-1][j];
if(j>=cost[i-1]){
f[i][j]=max(f[i][j],f[i][j-cost[i-1]]+1);
}
}
}
if(f[9][target]<0){
return "0";
}
string ans="";
int t=target;
for(int i=9;i>=1;i--){
while(t>=cost[i-1]&&f[i][t]==f[i][t-cost[i-1]]+1){
ans+='0'+i;
t-=cost[i-1];
}
}
return ans;
}
};
|
优化空间
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
| class Solution {
public:
int f[5001];
string largestNumber(vector<int>& cost, int target) {
for(int j=1;j<=target;j++){
f[j]=-0x3f3f3f3f;
}
for(int i=1;i<10;i++){
for(int j=cost[i-1];j<=target;j++){
f[j]=max(f[j],f[j-cost[i-1]]+1);
}
}
if(f[target]<0){
return "0";
}
string ans="";
int t=target;
for(int i=9;i>=1;i--){
while(t>=cost[i-1]&&f[t]==f[t-cost[i-1]]+1){
ans+='0'+i;
t-=cost[i-1];
}
}
return ans;
}
};
|
时间复杂度：$O(9*target)$，空间复杂度$O(target)$。
