class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
}
};
1449. 数位成本和为目标值的最大数字
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：
i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。target 。由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 "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 == 91 <= cost[i] <= 50001 <= target <= 5000原站题解
cpp 解法, 执行用时: 12 ms, 内存消耗: 9.1 MB, 提交时间: 2023-09-21 10:31:51
class Solution {
public:
string largestNumber2(vector<int> &cost, int target) {
vector<vector<int>> dp(10, vector<int>(target + 1, INT_MIN));
vector<vector<int>> from(10, vector<int>(target + 1));
dp[0][0] = 0;
for (int i = 0; i < 9; ++i) {
int c = cost[i];
for (int j = 0; j <= target; ++j) {
if (j < c) {
dp[i + 1][j] = dp[i][j];
from[i + 1][j] = j;
} else {
if (dp[i][j] > dp[i + 1][j - c] + 1) {
dp[i + 1][j] = dp[i][j];
from[i + 1][j] = j;
} else {
dp[i + 1][j] = dp[i + 1][j - c] + 1;
from[i + 1][j] = j - c;
}
}
}
}
if (dp[9][target] < 0) {
return "0";
}
string ans;
int i = 9, j = target;
while (i > 0) {
if (j == from[i][j]) {
--i;
} else {
ans += '0' + i;
j = from[i][j];
}
}
return ans;
}
// 优化
string largestNumber(vector<int> &cost, int target) {
vector<int> dp(target + 1, INT_MIN);
dp[0] = 0;
for (int c : cost) {
for (int j = c; j <= target; ++j) {
dp[j] = max(dp[j], dp[j - c] + 1);
}
}
if (dp[target] < 0) {
return "0";
}
string ans;
for (int i = 8, j = target; i >= 0; i--) {
for (int c = cost[i]; j >= c && dp[j] == dp[j - c] + 1; j -= c) {
ans += '1' + i;
}
}
return ans;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 39.4 MB, 提交时间: 2023-09-21 10:30:59
class Solution {
public String largestNumber2(int[] cost, int target) {
int[][] dp = new int[10][target + 1];
for (int i = 0; i < 10; ++i) {
Arrays.fill(dp[i], Integer.MIN_VALUE);
}
int[][] from = new int[10][target + 1];
dp[0][0] = 0;
for (int i = 0; i < 9; ++i) {
int c = cost[i];
for (int j = 0; j <= target; ++j) {
if (j < c) {
dp[i + 1][j] = dp[i][j];
from[i + 1][j] = j;
} else {
if (dp[i][j] > dp[i + 1][j - c] + 1) {
dp[i + 1][j] = dp[i][j];
from[i + 1][j] = j;
} else {
dp[i + 1][j] = dp[i + 1][j - c] + 1;
from[i + 1][j] = j - c;
}
}
}
}
if (dp[9][target] < 0) {
return "0";
}
StringBuffer sb = new StringBuffer();
int i = 9, j = target;
while (i > 0) {
if (j == from[i][j]) {
--i;
} else {
sb.append(i);
j = from[i][j];
}
}
return sb.toString();
}
// 优化
public String largestNumber(int[] cost, int target) {
int[] dp = new int[target + 1];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int c : cost) {
for (int j = c; j <= target; ++j) {
dp[j] = Math.max(dp[j], dp[j - c] + 1);
}
}
if (dp[target] < 0) {
return "0";
}
StringBuffer sb = new StringBuffer();
for (int i = 8, j = target; i >= 0; i--) {
for (int c = cost[i]; j >= c && dp[j] == dp[j - c] + 1; j -= c) {
sb.append(i + 1);
}
}
return sb.toString();
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.9 MB, 提交时间: 2023-09-21 10:30:18
func largestNumber2(cost []int, target int) string {
dp := make([][]int, 10)
from := make([][]int, 10)
for i := range dp {
dp[i] = make([]int, target+1)
for j := range dp[i] {
dp[i][j] = math.MinInt32
}
from[i] = make([]int, target+1)
}
dp[0][0] = 0
for i, c := range cost {
for j := 0; j <= target; j++ {
if j < c {
dp[i+1][j] = dp[i][j]
from[i+1][j] = j
} else {
if dp[i][j] > dp[i+1][j-c]+1 {
dp[i+1][j] = dp[i][j]
from[i+1][j] = j
} else {
dp[i+1][j] = dp[i+1][j-c] + 1
from[i+1][j] = j - c
}
}
}
}
if dp[9][target] < 0 {
return "0"
}
ans := make([]byte, 0, dp[9][target])
i, j := 9, target
for i > 0 {
if j == from[i][j] {
i--
} else {
ans = append(ans, '0'+byte(i))
j = from[i][j]
}
}
return string(ans)
}
// 优化
func largestNumber(cost []int, target int) string {
dp := make([]int, target+1)
for i := range dp {
dp[i] = math.MinInt32
}
dp[0] = 0
for _, c := range cost {
for j := c; j <= target; j++ {
dp[j] = max(dp[j], dp[j-c]+1)
}
}
if dp[target] < 0 {
return "0"
}
ans := make([]byte, 0, dp[target])
for i, j := 8, target; i >= 0; i-- {
for c := cost[i]; j >= c && dp[j] == dp[j-c]+1; j -= c {
ans = append(ans, byte('1'+i))
}
}
return string(ans)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 43.5 MB, 提交时间: 2023-09-21 10:29:33
/**
* @param {number[]} cost
* @param {number} target
* @return {string}
*/
var largestNumber2 = function(cost, target) {
const dp = new Array(10).fill(0).map(() => new Array(target + 1).fill(-Number.MAX_VALUE));
const from = new Array(10).fill(0).map(() => new Array(target + 1).fill(0));
dp[0][0] = 0;
for (let i = 0; i < 9; ++i) {
const c = cost[i];
for (let j = 0; j <= target; ++j) {
if (j < c) {
dp[i + 1][j] = dp[i][j];
from[i + 1][j] = j;
} else {
if (dp[i][j] > dp[i + 1][j - c] + 1) {
dp[i + 1][j] = dp[i][j];
from[i + 1][j] = j;
} else {
dp[i + 1][j] = dp[i + 1][j - c] + 1;
from[i + 1][j] = j - c;
}
}
}
}
if (dp[9][target] < 0) {
return "0";
}
const sb = [];
let i = 9, j = target;
while (i > 0) {
if (j === from[i][j]) {
--i;
} else {
sb.push(i);
j = from[i][j];
}
}
return sb.join('');
};
// 优化
var largestNumber = function(cost, target) {
const dp = new Array(target + 1).fill(-Number.MAX_VALUE);
dp[0] = 0;
for (const c of cost) {
for (let j = c; j <= target; ++j) {
dp[j] = Math.max(dp[j], dp[j - c] + 1);
}
}
if (dp[target] < 0) {
return '0';
}
const ans = [];
for (let i = 8, j = target; i >= 0; i--) {
for (let c = cost[i]; j >= c && dp[j] === dp[j - c] + 1; j -= c) {
ans.push(String.fromCharCode('1'.charCodeAt() + i));
}
}
return ans.join('');
};
python3 解法, 执行用时: 152 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-21 10:28:44
'''
该问题可以看作是恰好装满背包容量为 target，物品重量为 cost[i]，价值为 1 的完全背包问题。
定义二维数组 dp，其中 dp[i+1][j] 表示使用前 i 个数位且花费总成本恰好为 j 时的最大位数，
若花费总成本无法为 j，则规定其为 −∞。特别地，dp[0][] 为不选任何数位的状态，
因此除了 dp[0][0] 为 0，其余 dp[0][j] 全为 −∞。
'''
class Solution:
def largestNumber2(self, cost: List[int], target: int) -> str:
dp = [[float("-inf")] * (target + 1) for _ in range(10)]
where = [[0] * (target + 1) for _ in range(10)]
dp[0][0] = 0
for i, c in enumerate(cost):
for j in range(target + 1):
if j < c:
dp[i + 1][j] = dp[i][j]
where[i + 1][j] = j
else:
if dp[i][j] > dp[i + 1][j - c] + 1:
dp[i + 1][j] = dp[i][j]
where[i + 1][j] = j
else:
dp[i + 1][j] = dp[i + 1][j - c] + 1
where[i + 1][j] = j - c
if dp[9][target] < 0:
return "0"
ans = list()
i, j = 9, target
while i > 0:
if j == where[i][j]:
i -= 1
else:
ans.append(str(i))
j = where[i][j]
return "".join(ans)
'''
由于 dp[i+1][] 每个元素值的计算只与 dp[i+1][] 和 dp[i][] 的元素值有关，
因此可以使用滚动数组的方式，去掉 dp 的第一个维度。
去掉 from 数组。在状态倒退时，直接根据 dp[j] 与 dp[j−cost[i]]+1 是否相等来判断，
若二者相等则说明是从 dp[j−cost[i]] 转移而来，即选择了第 i 个数位。
'''
def largestNumber(self, cost: List[int], target: int) -> str:
dp = [float("-inf")] * (target + 1)
dp[0] = 0
for c in cost:
for j in range(c, target + 1):
dp[j] = max(dp[j], dp[j - c] + 1)
if dp[target] < 0:
return "0"
ans = list()
j = target
for i in range(8, -1, -1):
c = cost[i]
while j >= c and dp[j] == dp[j - c] + 1:
ans.append(str(i + 1))
j -= c
return "".join(ans)