我先把这道题真正“吃透”再给出一套可以直接落地的 Go 实现。这道题看起来像是 LeetCode 风格的构造题但它其实是在考一个非常经典的贪心直觉同样一个总和拆得越散平方和越小攒得越集中平方和越大。理解了这个点代码反而简单到只有十行。1. 题目到底在问什么拆开需求看本质先说结论题目要找的是一个num位正整数 (x)满足两个条件(x) 的十进制位数恰好是num(x) 各位数字之和恰好等于sum在所有这些 (x) 中求各位数字平方和的最大值。注意这里说的是“各位数字平方和”不是数字本身的大小。比如num 2, sum 10候选数有19、28、37、46、55、64、73、82、91。各位数字平方和分别是(1^2 9^2 82)(2^2 8^2 68)(3^2 7^2 58)(4^2 6^2 52)(5^2 5^2 50)……最大的是19或91平方和都是 82。这给了我们一个直观感受数字越往极端走平方和越大。1.1 两个约束条件之间的“张力”num限制了位数sum限制了数字和。换句话说我们其实是在做这样一件事把总和sum拆成num个一位数字09每一位就是这个正整数对应数位上的数字首位不能为 0然后计算每一位的平方之和使其最大。为什么把问题改写成“拆 sum”之后更好想因为一旦这么理解原题就不再是数字枚举题而是一个分配问题有num个盒子每个盒子能装 09 的“权重”权重总和要是sum目标是权重平方和最大。1.2 无解和绝对边界先判断再计算不是所有(num, sum)都有解。这里有几个硬边界sum最小是 1因为正整数各个数位之和至少为 1但更精确地说如果num 1那么首位至少是 1所以sum的最小值仍然是 1首位放 1后面全 0如果sum 0那只有 0 满足数位和但 0 不是正整数位数构成的正整数所以无解返回 -1sum最大不能超过 (9 \times num)。比如num 2两个数位的和最大是 18不可能得到sum 19。还有一个不太容易想到的边界num 1的时候数位只能是 19那么sum必须满足1 sum 9否则无解。提示这道题的边界很容易被忽略建议在实现里把“无解情况返回 -1”单独抽成判断函数防止后续构造数字时出现负值或超范围。2. 为什么贪心有效平方和的凸性这道题的核心既不是搜索也不是动态规划而是一个数学性质固定总和时平方和是凸函数值越集中平方和越大。2.1 先看一个反直觉的例子假设我们有两个位置数字和是 10。方案 A 是(5, 5)平方和是 (25 25 50)。方案 B 是(9, 1)平方和是 (81 1 82)。方案 C 是 (10, 0))但一位数字最大只能是 9所以不可行。从 50 到 82差距非常大。换句话说把 10 拆成两个 5远不如拆成一个 9 和一个 1 划算。这就是“集中”的优势。2.2 严格证明为什么“尽量填 9”是最优的要证明贪心策略的最优性可以用一个局部调整法假设某一位上是 (a)另一位上是 (b)且 (a b \le 9)。如果我们把这两位改成 ((ab, 0))平方和的变化是[ (ab)^2 0^2 - (a^2 b^2) 2ab \ge 0 ]这说明只要a b没有超过 9把两个数字合并到一个位置上平方和只会增加不会减少。如果a b 9那就不能合到一位去因为一位最多只能表示 9这时我们应该尽量把接近 9 的数值往一个位置堆。再换个角度用连续函数来看。如果允许每一位是任意实数那么固定总和 (S) 下最大化 (\sum x_i^2) 的最优解一定是 (x_1 S, x_2 0, \dots, x_n 0)。但由于每个数位上限是 9所以能塞 9 的位置就塞 9直到剩下的和小于 9。2.3 为什么不是构造“最大的数值”本身有人会想我是不是先构造出满足条件且数值最大的那个正整数然后求它的平方和但这是两码事。比如num 3, sum 15数值最大的方案是960平方和 (81360117)但其实最优的平方和方案是951或591(81251107)不对仔细算一下960是 117951是 107942是 101所以960确实也是平方和最大的。那这个例子看不出来。换一个num 3, sum 10。数值最大的方案是910平方和 (811082)还有901平方和也是 82但如果按“数值最大”构造确实也是 910。这说明在很多情况下两者方向一致但不完全是一回事。再找反例num 4, sum 10。数值最大的方案是9100平方和 82试一下9001平方和还是 82试一下8110平方和 (6411066)更小。看起来构造数值最大和平方和最大经常重合但不绝对。关键在于数值大小由高位决定平方和大小由所有位的取值分布决定。比如num 3, sum 19数值最大是991平方和 (81811163)平方和最大其实也是991因为 9 越多越好。那有没有数值最大但平方和不是最大的可以构造num 5, sum 20。数值最大尽量把大的数放高位99200平方和 (8181400166)但平方和最大应该尽量多用 999200用了两个 9、一个 2、两个 0看起来已经是最优了。其实这类题里“数值最大”和“平方和最大”的构造方向比较相似都是优先在高位放大的数字。但如果题目改成“各位数字乘积最大”或者“各位数字之和的立方最大”结论就会明显分化。对平方和来说每一位的取值比位置更重要因为平方和是个只和取值有关的对称函数而数值大小是位置敏感的。所以在做这类题时别把两个问题混为一谈时刻记住目标函数是“各位数字平方和”。2.4 贪心策略的最终形态根据上面的分析最优构造方案是用sum / 9算出能放多少个 9用sum % 9算出剩下一个余数 (r)如果 9 的个数已经达到num那说明所有位都是 9必须sum 9*num才成立否则放q个 9再放一个 (r)如果 (r) 不为 0剩下的位置全部填 0首位不能是 0所以当 (r0) 且 (qnum) 时要保证至少有一位非 0也就是 9。最大平方和公式[ \text{ans} q \times 9^2 r^2 ]其中 (q \lfloor sum / 9 \rfloor)(r sum \bmod 9)。但要先检查 (sum \le 9 \times num) 且 (sum \ge 1)否则无解。这里有个细节如果 (q num)那么 (r) 必须是 0否则sum 9*num已经无解了。也就是说在 (sum \le 9*num) 的前提下(q) 最大也就是num。直接用公式算不会出问题。3. Go 语言实现十行代码拿到最大值先给最终实现代码非常短核心逻辑就三个判断加一个公式。package main import fmt func maxSquareSum(num, sum int) int { // 无解情况一数位和不可能为 0正整数没有 0 位数 // 无解情况二num 位数的数位和最大就是 9*num if sum 1 || sum 9*num { return -1 } q : sum / 9 // 能放几个9 r : sum % 9 // 剩余余数 // 如果9的个数超过位数实际不可能但因为上面做了 sum 9*num 判断 // 这里一定满足 q num ans : q*81 r*r return ans } func main() { fmt.Println(maxSquareSum(2, 10)) // 82 fmt.Println(maxSquareSum(3, 15)) // 117 fmt.Println(maxSquareSum(1, 5)) // 25 fmt.Println(maxSquareSum(4, 0)) // -1 fmt.Println(maxSquareSum(2, 19)) // -1 }3.1 为什么不需要动态规划如果你第一反应是“这不就是背包/DP枚举每一位数字 09凑出和等于 sum求最大平方和”那说明你被很多数位 DP 题带偏了。这题和数位 DP 有本质区别数位 DP 通常涉及区间限制比如“不超过 N 的数里满足某条件的有几个”这题只有位数固定和数位和固定两个约束没有上限数字的约束一旦没有“上限”这个约束每一位之间就是完全独立的只有总和一个耦合条件。这种“无上限数位题”的最优解几乎都是贪心。因为目标函数 (\sum d_i^2) 是凸函数把资源集中到少数几个位置一定比分散更优。如果用 DP状态是“前 i 位和为 j 的最大平方和”复杂度是 (O(num \times sum \times 10))当num和sum达到 (10^6) 级别就彻底凉了。而贪心是 (O(1))。提示遇到“恰好 N 位、数位和为 S、求某些数位函数的最值”这类题先画一个“每个位置取值 09总和固定”的分配模型。如果目标函数是凸的基本靠贪心如果是“同时限制某个数位不能连续超过某个值”这类局部约束就得老老实实 DP。3.2 一个常见误区余数 r 能超过 9 吗r : sum % 9的结果一定在 08 之间天然合法。有些同学会把余数再拆成多个数字其实没必要。余数作为一个整体放在某一位上如果它是 0就不占位。如果它是 18就单独占一位。比如sum 26q2, r8构造(9,9,8)平方和 (818164226)。如果你是拆成(9,9,4,4)平方和只有 (81811616194)差远了。3.3 如果题目要求“输出那个数字本身”有些题目不只是问最大值还要求构造出来。比如“输出满足条件的任意一个最大平方和对应的正整数。”这个也简单只需要把 9 放在最高位余数放在次高位剩下的 0 放在低位同时注意首位不能是 0。构造代码如下func constructNumber(num, sum int) string { if sum 1 || sum 9*num { return -1 } digits : make([]byte, num) // 初始化每一位为 0 for i : range digits { digits[i] 0 } remaining : sum // 从最高位开始尽量放9但要留出余数 for i : 0; i num; i { if remaining 0 { break } if remaining 9 { digits[i] 9 remaining - 9 } else { digits[i] byte(0 remaining) remaining 0 } } // 如果最高位是0remaining为0且第一个数字没填需要调整 // 例如 num3, sum9第一轮会填9, 0, 0没问题 // 但如果 num4, sum0不可能因为sum至少为1。 // 唯一可能出现首位为0的情况是sum 9 且 num 1此时第一个数字直接是 sum // 不会为0。但如果构造时先填低位就危险了。 // 因此上面的循环从高位开始填天然正确。 res : string(digits) // 如果所有位都是0不可能sum1处理一下 return res }构造策略本质上是贪心地从高位到低位尽量放 9。这里要注意构造数字本身时优先在高位放 9 是为了让数字数值也尽量大但这不改变平方和。比如num3, sum10构造出来是910平方和 82但如果从低位开始填得到109平方和还是 82。两者平方和一样只是数值大小不同。所以需要根据题目要求选择高位优先还是低位优先。4. 靠对拍验证贪心别信直觉信数据我一直觉得对于这种公式化结论哪怕推导看起来再严谨也要写一个暴力解来对拍。尤其这道题边界情况多暴力枚举所有num位数虽然会超时但拿来验证小范围数据是极好的。4.1 暴力法怎么写枚举num位数的最小值到最大值之间的所有数字判断数位和是否为sum然后计算平方和取最大。func bruteMax(num, sum int) int { best : -1 start : 1 for i : 1; i num; i { start * 10 } end : start * 10 // 上限是开区间 for x : start; x end; x { digitSum : 0 squareSum : 0 tmp : x for tmp 0 { d : tmp % 10 digitSum d squareSum d * d tmp / 10 } if digitSum sum { if squareSum best { best squareSum } } } return best }这里没考虑前导零因为枚举本身就是从 10^{num-1} 开始的所以每个数正好是num位。暴力法在num 6的范围内可以很快跑完。4.2 对拍测试代码func TestCompare(t *testing.T) { for num : 1; num 5; num { for sum : 0; sum 9*num1; sum { got : maxSquareSum(num, sum) want : bruteMax(num, sum) if got ! want { t.Fatalf(num%d, sum%d, got%d, want%d, num, sum, got, want) } } } }跑完这个测试我观察到几个有意思的现象sum 0时贪心返回 -1暴力也是 -1因为最小的 num 位数是 (10^{num-1})数位和至少为 1sum 9*num时两个解法都返回 -1当num 1sum在 19 之间时贪心结果就是 (sum^2)暴力也只能取到这个数本身。提示写对拍测试时sum的范围不要只在 09*num 之间要带上sum0和sum9*num1这些越界值否则无解分支永远测不到。4.3 几个让人意外的测试用例光看公式可能觉得“这题也太简单了”但真去写边界测试时会发现几个反直觉的点。第一个是num 1, sum 7。从常识想个位数 7 的平方和是 49一定能得到。但如果代码里不小心把“首位不能为 0”落实到所有情况就可能在q 0, r 7的时候出问题。正确做法是把r直接放到最高位因为这里只有一位。第二个是num 3, sum 9。暴力结果是什么候选数字有108, 117, 126, 135, 144, 153, 162, 171, 180, 207,... 900其中平方和最大的是900(81)。注意900的数位和是 9平方和是 81不是最大的一个吗我们再看看810(641065)比 81 小540(2516041)。是的最大值就是 81。这正好对应公式q1, r0所以 (1 \times 81 0 81)。如果你构造时把 9 放中间或低位比如090不合法而900合法所以高位优先既符合数值最大也自然满足了首位非零。第三个是num 5, sum 36。q4, r0答案就是 (4 \times 81 324)。构造出来就是99990吗不对sum36如果四个 9 和一个 0和恰好是 36平方和是 (324)。但num5时最多只能有 5 位99990正好是 5 位满足条件。这也说明 9 可以放满四个位置剩下一个 0 放最后。5. 扩展一下同样的套路还能解决什么这道题虽然简单但它背后的思考方式可以迁移到很多“数位和”类的构造题。5.1 如果题目改成“求平方和的最小值”那就完全反过来最小值应该让所有数字尽可能平均。比如两位数和为 10平方和最小的是(5,5)即数字 55平方和 50。构造策略是尽量平均分配。但这里有个更微妙的点在数字只能取 09 的约束下平均分配不一定总能让每个数字都在 4 或 5 附近。比如num5, sum37直接平均(37/57.4)但每个位置最多 9所以答案是 7,7,7,8,8平方和是 (4949496464275)。这已经比全部集中到 99991(818181811325)小很多。如果要求最小值一个简单贪心是先把sum / num作为每一位的初值再把余数均匀分配到后面的若干位上每位最多加 1直到余数为 0。注意首位不能为 0 的限制如果sum / num 0说明 sum 小于 num那么首位至少放 1其余位放 0余数再调整平方和会稍大一点。5.2 什么时候必须上 DP而不是贪心如果约束变成“任意相邻两位的差不能超过 1”或者“不能出现连续两个 0”这个时候每一位之间不再独立贪心就会失效。举一个经典例子求一个num位数数位和为sum且相邻两位差的绝对值不超过 1任意一位不能为 0求最大平方和。这种情况下你大幅增加某一位的值会影响相邻位选择就不再是全局独立的。此时就得用 DPdp[i][j][last]表示前i位和为j、最后一位为last的最大平方和复杂度 (O(num \times sum \times 10 \times 10))。在这道题里完全不需要但知道边界在哪里才能不把贪心滥用。5.3 如果 num 和 sum 都极大怎么办num是 10^9sum也是 10^9 级别那答案直接按公式算即可连数组都不用开。Go 的int在 64 位机器上范围足够。唯一可能溢出的是q*81比如sum10^9时q ≈ 1.11e8乘以 81 大约是 (9 \times 10^9)int64完全能扛住。但如果题目要求构造出“那个数字”就要输出一个长度 10^9 的字符串这时候需要调用strings.Builder或者bytes.Buffer来高效拼接不能再用[]byte一个个分隔赋值。代码示例如下func constructHuge(num, sum int) string { if sum 1 || sum 9*num { return -1 } var sb strings.Builder q : sum / 9 r : sum % 9 // 先放 q 个 9如果 q 超过 num不会发生因为已经判断 sum 9*num for i : 0; i q; i { sb.WriteByte(9) } // 放余数 if r 0 { sb.WriteByte(byte(0 r)) } // 补0到num位 for i : q; i num; i { if r 0 { // 已经写过r了这里要跳过一位 } sb.WriteByte(0) } // 但上面这种写法有bug需要记录已经写了几个数字 // 正确做法见下文 }构造超大数字时要尤其注意“已经写了几位”的状态别把 r 那一位漏掉或者多补一位 0。用written变量记录最稳妥。func constructHuge(num, sum int) string { if sum 1 || sum 9*num { return -1 } var sb strings.Builder written : 0 q : sum / 9 r : sum % 9 // 如果 9 的个数已经占满所有位直接全是9 if q num { for i : 0; i num; i { sb.WriteByte(9) } return sb.String() } // 先放 q 个 9 for i : 0; i q; i { sb.WriteByte(9) written } // 放余数如果有的话 if r 0 { sb.WriteByte(byte(0 r)) written } // 剩余补0 for i : written; i num; i { sb.WriteByte(0) } return sb.String() }这段代码在sum 9的情况下也能正确输出比如num3, sum5q0,r5先写一个5然后补两个0得到500平方和 25确实是最大值。5.4 这类题在真实开发里有什么用可能有人觉得算法题就是刷题用但“数位平方和最大”这种分配问题其实可以映射到资源调度上。比如你有sum份资源最多往num个桶里放每个桶容量为 9收益是容量的平方。这就是变形的“集中投资”模型在有限仓位里与其平均分摊资源不如集中到几个高收益仓位上。现实中类似的场景有带宽分配、GPU 显存划分、预算分配到多个广告组等。当然现实约束往往更复杂但“凸收益函数下集中优于分散”这个直觉在很多优化问题里都能迁移。6. 小结还是算了说点实在的踩坑记录这道题我在写第一版的时候踩了两个坑说出来大家引以为戒。第一个坑一开始我没做sum 9*num的边界判断直接用q : sum / 9去乘 81。结果num2, sum25的时候算出q2, r7答案2*8149211但实际两个数位根本凑不出 25答案应该是 -1。后来才补上边界判断。这个错误特别隐蔽因为公式本身不会报错只会给出“看似合理”的错误答案。第二个坑构造数字时如果r 0我不小心多写了一位 0。比如num3, sum18正确构造是990但我写出9900变成了 4 位数完全不符合位数要求。更隐蔽的是如果直接for i : 0; i q; i写 9再if r 0写 r最后for i : q; i num; i补 0那在r0时会多写一个 0。所以用written变量统一计数是更稳妥的写法。还有一个小经验测试用例里一定要包含“能整除 9”的边界和“刚好等于 9*num”的边界。sum9*num时应该全部是 9没有 0这是最容易出错的地方。这段代码如果给你之后你完全可以把它封装成一个函数直接扔进自己的工具库。以后遇到类似的“固定位数、固定数位和、求数位平方和极值”的问题第一反应就是先看目标函数是否“凸”如果是用贪心不是再考虑 DP。我个人在刷了这道题之后再看很多数位构造题的套路都清晰了很多希望这篇能把同样的感觉带给你。