Leetcode 数位成本和目标值的最大数字
题目链接: leetcode 1449.数位成本和为目标值的最大数字
题目
给你一个整数数组 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 (DP动态规划))
思路分析
首先题目要求解的是得到一个最大的数字, 考虑这个最大的数字有什么特征, (1) 数字长度最长 (2) 数字长度相同的情况下依次从最高位开始比。 我们可以得知 (1) 条件是一个优先条件, 故我们可以先把这个数字的最大长度选出来. 这里的限制是
- 只能在 1 ~ 9 的数字中选, 每个数字所选的次数不限
- 且所选的所有数字的总成本恰好等于 target
故我们求这个最大数字的总长度实际就相当于是一个背包问题, 每个数字的成本相当于每件物品的体积, 背包的容量为 target, 每个数字即每个物品的价值为1, 总价值相当于总长度. 只不过这里需要的是最后刚好装满背包. 由于每个数字所选次数不限制. 故这就是一个完全背包问题, 故先用完全背包思路求出我们数字的最大长度. f[i][j]表示的是在数字 1 ~ i 中选, 且所选数字的总成本为j 的方案中数字最大的长度。
求出能够满足总成本为target的数字的最大长度n之后我们就可以开始从高位开始填数, 故这里就要运用我们上面分析的第二条性质, 从高位开始依次填, 我们先从9 ~ 1 开始依次填数, 如何判断我们是否可以填了数字x, 若数字x可以填入, 则此时填入后剩下的数字长度为 n - 1, 且由于填了数字x, 故此时总成本为 target - cost[x - 1], 故我们f[target - cost[x - 1]] == n - 1是否成立, 若这个关系成立, 说明填入x可行, 说明存在一种方案使得总成本 target - cost[x - 1] 的情况下其数字长度为 n - 1;
C++ 代码
class Solution
{
public:
string largestNumber(vector<int>& cost, int target)
{
int f[5010];
memset(f, 0x80, sizeof f); // 初始化为一个很小的值
f[0] = 0; // target为0时,满足条件为不选任何数位的状态, 故数字的长度为0
for(int i = 1; i <= 9; ++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"; // 若总成本为target的情况下, 数字总长度 < 0 表示无任何方案
string res;
int len = f[target];
for(int i = 9; i; --i) // 从9 ~ 1
while(target - cost[i - 1] >=0 && f[target - cost[i - 1]] == len - 1)
target -= cost[i - 1], --len, res += to_string(i); // 若该数字满足条件选上
return res;
}
};
Python 代码
class Solution:
def largestNumber(self, cost: List[int], target: int) -> str:
f = [int(-1e+8)] * 5010
n = len(cost)
f[0] = 0
for i in range(1, n + 1):
for j in range(cost[i - 1], target + 1):
f[j] = max(f[j], f[j - cost[i - 1]] + 1)
if(f[target] < 0): return "0"
res, l = [], f[target]
for i in range(9, 0, -1):
while(target - cost[i - 1] >= 0 and f[target - cost[i - 1]] == l - 1):
target -= cost[i - 1]
l -= 1
res.append(str(i))
return "".join(res)