LeetCode 1449. 数位成本和为目标值的最大数字
题目描述
题意分析
选择数字一到九拼成一个尽可能大的正整数，每写一位数字
d都要支付cost[d - 1]，同一个数字可以使用多次。总费用必须恰好等于target，不能只要求不超过预算，也不能剩下一部分不用。目标是数值最大，不是单个数字最大或总位数最多后随便排列。由于答案可能远超整数类型范围，需要返回字符串；如果不存在任何恰好花完预算的数字，返回字符串
"0"。零不是可选择的数位，只是无解标记。
解法：DP 长度 + 贪心重建
核心思路
[!blue]
没有零数位时，位数更多的整数一定更大；只有位数相同，才需要比较从高位到低位的字典序。因此先用动态规划求最多能写多少位，再在不损失位数的前提下尽量把大数字放在前面，把两个优化目标分开处理。
定义
dp[t]为恰好花费t能写出的最大位数。若最后选择数字d，此前必须恰好花费t - cost[d - 1]，并增加一位，所以枚举所有费用不超过t的数字，取dp[t - cost[d - 1]] + 1的最大值。费用都为正，依赖的是更小成本，按成本递增计算即可；数字可重复，所以不限制此前是否已经使用过它。只有
dp[0] = 0初始可达，其余状态要用负数表示不可达，不能当成零位方案。代码使用-target - 1：每写一位至少消耗一单位成本，全部转移最多增加target次，即使从负状态继续加一，仍保持负数，不会冒充合法长度。最终dp[target] < 0就说明无法恰好花完预算。重建时设剩余成本为
t，要保留的最优位数为dp[t]。尝试写下数字d后，只有满足dp[t] == dp[t - cost[d - 1]] + 1，剩余成本才仍能完成所需位数；否则写这个数字会损失长度，不能选。满足条件的数字中优先选九，再依次尝试更小数字，保证当前最高未定数位尽可能大。同一个大数字只要继续满足条件，就可以不断追加。转向更小数字后也不用回头：若某个更大数字能出现在后续最优方案中，交换数位顺序不改变费用和位数，它本来就能提前放到当前位，与此前不能选择它矛盾。因此从九到一一次下降枚举，就能构造同长度中字典序最大的答案。
每次成功追加都会减小正成本并减少一位最优长度，最终成本归零，恰好构造出
dp[target]位。整个过程只保存长度表，不必在每个状态里复制完整字符串。
解题步骤
- 将长度表初始化为负哨兵，仅令
dp[0] = 0。- 从成本一递增到
target，枚举数字一到九，使用较小成本状态加一更新最大位数。- 目标状态仍为负时返回
"0"。- 否则从数字九到一依次尝试，剩余预算足够且满足最优长度等式时，反复追加该数字并扣减成本。
- 返回构造出的数字字符串。
代码实现
class Solution {
public String largestNumber(int[] cost, int target) {
// dp[t]：恰好花掉代价 t 时能写出的最多位数；负数代表不可达。
int[] dp = new int[target + 1];
Arrays.fill(dp, -target - 1);
dp[0] = 0;
for (int t = 1; t <= target; t++) {
for (int d = 1; d <= 9; d++) {
int c = cost[d - 1];
if (t >= c) {
// 负状态加一可能被更新，但仍为负数，不会冒充合法长度。
dp[t] = Math.max(dp[t], dp[t - c] + 1);
}
}
}
if (dp[target] < 0) {
return "0";
}
StringBuilder sb = new StringBuilder(dp[target]);
int t = target;
for (int d = 9; d >= 1; d--) {
int c = cost[d - 1];
// 只要写下 d 不损失总长度，就一直写，先把高位铺满大数字。
while (t >= c && dp[t] == dp[t - c] + 1) {
sb.append(d);
t -= c;
}
}
return sb.toString();
}
}
func largestNumber(cost []int, target int) string {
// dp[t]：恰好花掉代价 t 时能写出的最多位数；负数代表不可达。
dp := make([]int, target+1)
for i := range dp {
dp[i] = -target - 1
}
dp[0] = 0
for t := 1; t <= target; t++ {
for d := 1; d <= 9; d++ {
c := cost[d-1]
if t >= c {
// 负状态加一可能被更新，但仍为负数，不会冒充合法长度。
if dp[t-c]+1 > dp[t] {
dp[t] = dp[t-c] + 1
}
}
}
}
if dp[target] < 0 {
return "0"
}
res := make([]byte, 0, dp[target])
t := target
for d := 9; d >= 1; d-- {
c := cost[d-1]
// 只要写下 d 不损失总长度，就一直写，先把高位铺满大数字。
for t >= c && dp[t] == dp[t-c]+1 {
res = append(res, byte('0'+d))
t -= c
}
}
return string(res)
}
复杂度分析
- 时间复杂度：
O(target)。每个成本枚举固定九种数字，重建长度不超过target，成功追加和下降数字的总次数也是线性量级。- 空间复杂度：
O(target)。长度表和结果构造缓冲都不超过预算量级。
关键点总结
[!green]
- 整数大小先比较位数，再比较同长度的字典序，不能一开始只追求大数位。
- 恰好凑成本需要区分不可达状态，负数不能当作合法零位结果。
- 重建等式保证当前选择不损失最优长度，大数字优先再保证数值最大。
- 数位可交换且成本与位置无关，使从九到一的连续重建成立。
易错点总结
[!yellow]
- 全部状态初始化为零：会把凑不出的剩余成本当成可达，制造没有恰好花完的假方案。
- 只选当前能买得起的最大数字：可能浪费成本而少写一位，整体数值反而更小。
- 重建不检查长度等式：预算足够不代表剩余成本可达，也不代表能保持最多位数。
- 每个数字只判断一次：同一数字允许重复，需要在可行时连续选择。
- 从一到九重建：即使长度正确，也会把小数字放在高位，无法得到最大数。
- 用固定整数类型累积答案：结果可能很长，应直接构造并返回字符串。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 322. 零钱兑换 | 中等 | 同样可重复选择费用项并要求总成本恰好匹配，本题先最大化位数，再按字典序重建最大数。 |