LeetCode 1449. 数位成本和为目标值的最大数字
目录
题目描述
题意分析
给定长度为 9 的数组
cost，cost[d-1]是写下数字d（d从 1 到 9）要花的代价，以及一个正整数target。要拼出一个整数，使得所有数位的代价之和恰好等于target（不是不超过，是严格相等），并且这个整数尽可能大。拼不出来就返回字符串"0"。
有几个约束把解法框得很死。第一，可用数位只有 1 到 9，没有 0，所以不存在前导零问题，任何数位排列都是合法数字。第二，每个数字可以重复使用任意多次，这是完全背包的形态而不是 0/1 背包。第三，代价必须恰好用完，所以「不可达」是一个必须被显式表示的状态，不能用 0 混过去。
「尽可能大」这个目标要拆成两个层次，顺序不能颠倒：位数多的数一定更大（因为没有 0，任何 9 位数都大于任何 8 位数）；位数相同时，从高位开始逐位比较，高位越大越好。这个词典序规则是整道题的骨架——它告诉我们优化目标其实是「先最大化长度，再在最长的前提下最大化字典序」。
规模上
target到 5000，cost[i]到 5000，只有 9 种数字，所以 $O(9 \cdot target)$ 的表格完全可行。答案的位数最多约 5000 位，远超long范围，必须用字符串返回，任何试图用数值累加的写法都会溢出。
边界：
target小于所有cost的最小值时一位都写不出，返回"0"；某些target即使大于最小代价也可能因为余数凑不齐而不可达，例如cost全是 2 而target是奇数。
解法：DP 长度 + 贪心重建
核心思路
直接搜索所有数位组合是指数级的。第一层观察是把目标拆成两阶段：既然位数优先于字典序，那就先只求最大位数，再在保证位数最大的前提下贪心地决定每一位填什么。这两步可以完全解耦。
第一阶段是标准的完全背包求最大件数。定义状态：
dp[t]表示恰好花掉代价t时，能写出的最多数位个数；若代价t无法被恰好凑出，则dp[t]为负无穷（不可达）。
转移就是枚举最后写下的那一位是哪个数字：
\[dp[t] = \max_{1 \le d \le 9,\ t \ge cost[d-1]} \big(dp[t - cost[d-1]] + 1\big)\]
初始条件
dp[0] = 0：花掉 0 代价能写出 0 位数字，这是唯一的合法起点。其余状态设为-target-1。从一个不可达状态出发，即使沿转移错误地累计最多target次+1，值仍小于 0；因此它既不会压过合法状态，也不会被误判为可达。这里不能初始化为 0，否则「凑不出t」会被当成「凑出了 0 位」，进而污染整张表。
外层枚举
t从小到大、内层枚举d，这个顺序天然满足完全背包「同一物品可重复取」的要求——dp[t - cost]在本轮之前就已经算完，且它自身也可能已经用过数字d。
第二阶段是贪心重建。有了
dp表，从最高位开始逐位决定：优先尝试大的数字。对当前剩余代价t，从d = 9往下试，只要t >= cost[d-1]且dp[t] == dp[t - cost[d-1]] + 1，就说明「在位置上写下d，剩下的代价t - cost[d-1]仍能凑出dp[t] - 1位」，即写d不会损失任何长度，那就贪心地写它，并且用while一直写到写不动为止。
这个贪心之所以正确，正是因为条件
dp[t] == dp[t-c] + 1保证了长度不受损；在长度不受损的所有选择里，越靠前的位越大就越优，而当前正是最高位。贪心不变量可以写成：每次追加一个数字后，t与dp[t]依旧同步——剩余代价t恰好还能凑出dp[t]位，且已输出的前缀是所有最优解中字典序最大的前缀。因为从 9 递减枚举，先被写满的一定是尽可能多的大数字。
解题步骤
- 开表并初始化：
dp长度为target + 1，先全部填成-target-1，再令dp[0] = 0。这个哨兵由输入上界直接推出：任何转移链最多追加target位，所以不可达值无论经过多少次+1都仍为负数，不需要魔法常量。- 正序填表：
t从 1 到target，内层d从 1 到 9，先判断t >= cost[d-1]再松弛。这里不需要额外判断dp[t - c]是否可达：不可达时它是一个巨大的负数，+1后仍然远小于任何合法值，不会被max选中，负无穷起到了自动过滤的作用。- 判无解：
dp[target] < 0说明代价凑不齐，按题意返回字符串"0"。这一步必须在重建之前做，否则重建循环会因为条件永不成立而返回空串。- 从高位到低位贪心重建：
t = target，d从 9 递减到 1；内层while (t >= c && dp[t] == dp[t - c] + 1)时追加字符d并t -= c。用while而不是if是关键——同一个大数字能连写几位就连写几位，先把高位铺满大数字才是字典序最大。- 拼接返回：Java 用
StringBuilder追加，Go 用[]byte追加后转字符串，避免 $O(n^2)$ 的字符串拼接。重建自然是从高位往低位产生的，不需要反转。
以
cost = [4, 3, 2, 5, 6, 7, 2, 5, 5]、target = 9走一遍。也就是写 1 花 4、写 2 花 3、写 3 花 2、写 4 花 5、写 5 花 6、写 6 花 7、写 7 花 2、写 8 花 5、写 9 花 5。
填表阶段，最小代价是 2（数字 3 和 7 都是 2）：
dp[0] = 0。
dp[1]：没有代价 ≤ 1 的数字，不可达。
dp[2] = dp[0] + 1 = 1（用 3 或 7）。
dp[3] = dp[0] + 1 = 1（用 2）。
dp[4] = max(dp[2] + 1, dp[0] + 1) = 2（两个 2 代价的数字，或一个 1）。
dp[5] = max(dp[3] + 1, dp[2] + 1, dp[0] + 1) = 2。
dp[6] = dp[4] + 1 = 3。
dp[7] = dp[5] + 1 = 3。
dp[8] = dp[6] + 1 = 4。
dp[9] = dp[7] + 1 = 4。
所以最长能写 4 位。
dp[9] = 4 >= 0，有解，进入重建。
重建阶段，
t = 9：
d = 9（代价 5）：dp[9] = 4，dp[4] = 2，2 + 1 = 3 ≠ 4，写 9 会让总长掉到 3，跳过。
d = 8（代价 5）：同样不成立，跳过。
d = 7（代价 2）：dp[7] = 3，3 + 1 = 4 = dp[9]，成立！追加7，t变成 7。再试：dp[5] = 2，2 + 1 = 3 = dp[7]，成立，追加7，t变成 5。再试：dp[3] = 1，1 + 1 = 2 = dp[5]，成立，追加7，t变成 3。再试：dp[1]不可达，dp[1] + 1是巨大负数，不等于dp[3] = 1，停止。当前结果"777"。
d = 6（代价 7）：t = 3 < 7，跳过。d = 5（代价 6）、d = 4（代价 5）同样跳过。
d = 3（代价 2）：dp[1]不可达，不成立，跳过。
d = 2（代价 3）：dp[0] = 0，0 + 1 = 1 = dp[3]，成立，追加2，t变成 0。再试：t = 0 < 3，停止。结果"7772"。
d = 1（代价 4）：t = 0，跳过。
返回
"7772"，正好 4 位，代价2 + 2 + 2 + 3 = 9，与target严格相等。可以对照一下：同样是 4 位的还有7773吗？写 3 也花 2，但四个 2 代价的数字总共只花 8，剩 1 凑不齐，所以 4 位方案里代价分配只能是2+2+2+3，末位必须是代价 3 的数字 2。而把7换成3只会让高位变小。贪心从 9 往下、能连写就连写，正好选中了7772。
代码实现
import java.util.Arrays;
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) {
// 不可达状态是极小负数，+1 后不会被 max 选中，无需额外判断。
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 {
// 不可达状态是极小负数，+1 后不会被选中，无需额外判断。
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(9 \cdot target)$，即 $O(target)$。填表阶段是
target乘以固定的 9 种数字；重建阶段每追加一位至少消耗 1 点代价，总追加次数不超过target，外层 9 次循环也是常数，所以重建同样是 $O(target)$。- 空间复杂度：$O(target)$。一维
dp数组占target + 1个整数；答案字符串最长约target / min(cost)位，最坏也是 $O(target)$ 量级，属于必需的输出开销。相比记录完整转移路径的写法，本解法靠「用dp表反推」省掉了额外的决策数组。
关键点总结
- 把「求最大数」拆成「先最大化位数、再最大化字典序」，是本题的核心分解。位数是可加的、适合 DP；字典序不可加、适合贪心。看到「构造最优字符串」的题，先想能不能这样分层是通用打法。
- 不可达必须用负无穷显式表示，不能用 0。恰好装满型背包和「不超过」型背包的唯一区别就在初始化上，这是面试里最常被追问的一点。
- 靠
dp[t] == dp[t-c] + 1反推路径，不需要额外的choice数组。这个技巧在所有「求方案而不只求最优值」的 DP 里都能用，省一个数组也省一次同步维护。- 重建时用
while而非if：字典序最大要求尽可能多的高位是大数字，能连写就连写。写成if会让每个数字最多出现一次，答案立刻变小。- 答案必须是字符串：
target到 5000 意味着结果可能有数千位，用long或int存都会溢出。看到「返回最大数字」先确认返回类型，是很实用的审题习惯。- 完全背包的「外层容量、内层物品」和「外层物品、内层容量」在本题都能算出正确的
dp，但前者更贴合「枚举最后一位是谁」的推导叙述，面试时讲起来更顺。
易错点总结
dp全部初始化为 0：cost = [2,2,2,2,2,2,2,2,2]、target = 3时，错误转移会由不可达的dp[1] = 0推出dp[3] = 1，并重建出代价只有 2 的"9"；正确答案是"0"。- 负无穷离 0 太近：若哨兵只取
-1，上面的不可达状态加一次就变成 0，继续转移后甚至会变成正数。用-target-1可由「最多追加target位」直接证明安全。- 重建时用
if代替while：cost = [4,3,2,5,6,7,2,5,5]、target = 9会先写一个7（t变 7），然后d继续往下递减，再也回不到 7，最终得到位数不足的短串（如"732"），而正确答案是"7772"。- 重建时从
d = 1递增到 9：同一用例会优先塞小数字，得到"2333"这个同样 4 位但字典序更小的结果。方向必须是 9 → 1。- 忘记
dp[target] < 0的无解判断：cost = [5,5,5,5,5,5,5,5,5]、target = 3时重建循环里所有条件都不成立，返回空字符串""，而题目要求返回"0"。- 把结果按数值累加（如
answer = answer * 10 + d）：target = 5000且最小代价为 2 时答案有 2500 位，long早在第 19 位就溢出，输出完全是垃圾值。- 用
String做+=拼接：答案可达数千位，每次拼接都重新分配并复制，时间退化到 $O(target^2)$，target = 5000时明显变慢。cost的下标偏移写错，把cost[d]当成数字d的代价：cost长度只有 9，d = 9时cost[9]直接越界；即使不越界，每个数字都对应错了代价，答案全错。- 误以为可以用数字 0：题目只给了 1 到 9 的代价，若在重建时允许写 0，
"70"这类结果既没有对应代价也不合题意。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 322. 零钱兑换 | 中等 | 恰好装满求最少件数，负无穷换成正无穷，是本题填表阶段的镜像 |
| 518. 零钱兑换 II | 中等 | 求方案数而非最优值，循环顺序决定组合还是排列，初始化改为 dp[0]=1
|
| 377. 组合总和 Ⅳ | 中等 | 同样计数但顺序不同视为不同方案，必须外层容量内层物品 |
| 279. 完全平方数 | 中等 | 物品集合由平方数动态生成，其余与最少件数背包完全一致 |
| 面试题 08.11. 硬币 | 中等 | 固定四种面额的计数型完全背包，额外考察取模防溢出 |
| LCR 103. 零钱兑换 | 中等 | 与 322 同题，可用来练习恰好装满的初始化写法 |