第 168 场双周赛的 Q2题目编号 3723名字叫“数位平方和的最大值”。这道题我在比赛时花了 8 分钟 AC属于典型的“看着像难题、实际有套路”的送分题。很多选手卡住是因为一开始就想着暴力枚举看到 n 的范围直接懵了但只要把“平方和”和“不超过 n”这两个条件拆开看解法非常清晰。本文我会从暴力解法讲起逐步推导出两个可 AC 的方案候选数枚举和数位 DP再把比赛现场容易踩的边界坑全部列出来适合正在刷双周赛、准备突破 Q2 的选手参考。1. 题目解读数位平方和到底在求什么1.1 数位平方和的定义先统一概念。给定一个非负整数 x把它拆成十进制位每一位平方后再求和就是数位平方和。比如 x 123数位平方和是 1^2 2^2 3^2 14x 99数位平方和是 81 81 162x 0数位平方和是 0。这个定义和力扣 202 题“快乐数”里的计算方式一模一样但问题完全相反快乐数是反复用这个操作直到收敛而本题是在一个区间里找数位平方和最大的那个值。题目给定一个非负整数 n要求在 [0, n] 范围内找一个整数使它的数位平方和最大返回这个最大值。注意绝大多数版本只要求返回最大值不要求返回对应的数不过有些变体可能会要求返回原数我会在后面补充怎么改代码。一个容易混淆的点是“数位和”和“数位平方和”。数位和是 1 2 3 6数位平方和是 1 4 9 14。因为平方的存在同一数量级下一个高位上的 9 对结果的贡献是 81而低位上的 9 同样也是 81。这意味着什么意味着我们在固定数字位数时每一位都尽量接近 9 是收益最高的策略这个特性直接决定了本题的解法。1.2 数据范围决定不能暴力先给出最暴力的思路枚举 0 到 n 的每一个数求出每个数的数位平方和取最大值。Python 代码大概是这样的def max_digit_square_sum_brute(n: int) - int: ans 0 for x in range(n 1): cur x s 0 while cur: d cur % 10 s d * d cur // 10 ans max(ans, s) return ans这个解法本身没有任何问题问题出在 n 的范围上。LeetCode 这类题里n 通常是 10^9 甚至 10^18 级别。如果 n 10^9Python 要跑十亿次循环每次还有内层取位操作整体耗时几十秒比赛环境直接超时。如果把 n 上升到 10^18这就不是慢几倍的问题而是彻底不可行。所以本题真正要解决的核心问题不是“怎么算数位平方和”而是“如何跳过大量无用的数只考察极少数候选数字”。大多数人对“数位 DP”这个词有心理负担其实这道题根本不需要先上数位 DP有一个更简单的贪心构造方法30 行代码就能写完。1.3 先建立直觉答案长什么样我先举几个例子找感觉。n 19 时0 到 19 里所有数的数位平方和如下19 本身是 1 81 8218 是 1 64 6517 是 509 是 81。最大是 82对应的就是 n 本身。再看 n 100100 自己的数位平方和是 1而 99 的数位平方和是 81 81 162显然 162 更大。再看 n 200200 自己是 4而 199 是 1 81 81 163。最大值在 199 身上。这些例子说明最优答案不一定在 n 本身而往往会落在“某一位比 n 少 1后面全是 9”的数字上。99、199 都属于这种形态。这个直觉就是贪心解法的核心后面我会严格证明为什么只需要看这些候选数。2. 贪心构造为什么候选数只需要枚举“某一位减 1后面全补 9”2.1 平方函数的凸性让 9 成为最优值为什么“后面全是 9”很重要因为数位平方和中每一位的贡献是该位数字的平方而各个数位之间是完全独立的。固定其他位不变时某一位从 d 提高到 d 1额外收益是 (d 1)^2 - d^2 2d 1。d 越大再加 1 的收益越高这体现了平方函数在非负整数上的凸性。换句话说数字越大继续增大的“边际收益”越高所以在不受限制的情况下每一位都会选择最大值 9。单纯看单个数字9^2 81而 8^2 6410^2 虽然更大但 10 不是一个数位需要进位。在十进制一位数里9 是绝对值最高的数位。于是可以想象如果某个位置已经不受 n 的上界约束那么它后面所有位数都应该填 9。比如 n 100 时只要第一位取 0第二位和第三位都取 9得到 99平方和就达到 162。这里有一个经验上的小提醒数位平方和问题里不要用“数字越大越好”来替代“数位平方和越大越好”。数字 100 比 99 大但平方和 1 远小于 162。所以目标函数和数值大小没有单调关系我们必须从数位的角度去想而不是从整数的角度去想。2.2 严格论证最优解一定是候选形态现在来证明候选形态的完备性。设最优解为 y且 y n。如果 y n那么 y 本身就是一个候选。如果 y n我就可以找到从左到右第一个 y 与 n 不同的位置 i。在这个位置之前y 的前缀和 n 完全一样在第 i 位y_i 一定小于 n_i。既然第 i 位已经小于 n_i那么从 i 1 位开始y 的后续所有位都不再受 n 的限制。此时为了让平方和最大这些后续位每一位都应该取 9否则把某个非 9 的位改成 9数仍然小于 n平方和却能增加这与“最优”矛盾。再看第 i 位本身。y_i 的取值范围是 0 到 n_i - 1由于后续位已经取满 9第 i 位也应当取最大值 n_i - 1因为把这一位增大到 n_i - 1 后整个数仍然小于 n平方和增大。如果 y_i 比 n_i - 1 还小把它提上来只会更好。因此所有 y n 的最优解必然形如“前缀与 n 相同第 i 位取 n_i - 1后缀全部取 9”。这就把最优解的搜索空间从 [0, n] 缩小到最多 len(n) 1 个候选数字n 本身以及每个位置“减 1 后补 9”的数。即使 n 有 10^18 那么大十进制位数也只有 19 位所以这个做法的时间复杂度是 O(len(n)^2)完全可以在瞬间算完。2.3 候选枚举的完整实现与边界处理根据上面结论代码就很简单先把 n 转成字符串对每一位去构造候选数。完整实现如下def max_digit_square_sum(n: int) - int: s str(n) ans 0 # 计算某个数的数位平方和 def calc(x: int) - int: total 0 while x: d x % 10 total d * d x // 10 return total # 候选 1n 本身 ans calc(n) # 候选 2某一位减 1后面全补 9 for i in range(len(s)): if s[i] 0: continue prefix s[:i] current int(s[i]) - 1 candidate_str prefix str(current) 9 * (len(s) - i - 1) candidate int(candidate_str) ans max(ans, calc(candidate)) return ans几个细节值得展开说。遇到 s[i] 0 时直接 continue不要 break。比如 s 100在 i 0 时得到候选 099去掉前导零后是 99这正是最大答案的来源如果错误地在 i 0 之后 break后面就不看了答案就会漏掉。而在 i 1 和 i 2 时s[1] 0、s[2] 0直接跳过因为某一位是 0 的话减 1 会产生借位这种形态实际上会被更前面的减 1 操作覆盖掉不需要重复考虑。用 int(candidate_str) 转整数时Python 会自动去掉前导零所以 099 会变成 99。这个行为在这里帮了我们不需要手动做 strip(0)。但如果你用的是 C用 stoll 同样会自动处理前导零效果一样。这个解法的时间复杂度严格说是 O(L^2)其中 L 是 n 的十进制位数。L 最大也就是 19所以完全可以认为是常数时间。空间复杂度 O(L)。相比暴力枚举优化是压倒性的。3. 数位 DP 解法把这类问题模型化成记忆化搜索3.1 数位 DP 的状态设计与思想如果题目加了额外的限制条件比如要求数位平方和恰好等于某个值或者要求返回那个数本身候选枚举可能就不够用了。这时候需要更通用的数位 DP。数位 DP 的核心思想是从高位到低位逐位填数字同时维护两个状态当前是否严格贴着 n 的上界tight以及当前是否已经填过非零数字started。第一个状态保证构造出的数严格不超过 n第二个状态用于处理前导零。状态设计好后用记忆化搜索缓存“当前位之后能获得的最大后缀贡献”。具体来说定义 dfs(pos, tight, started) 表示正在填第 pos 位此前填过的数与 n 的前缀相等tightTrue或已经小于 ntightFalse以及此前是否已经填过一个非零数字。函数返回值是从第 pos 位到最后一位能产生的最大数位平方和贡献。这里有一个初学者容易忽略的细节为什么要管 started因为在计算平方和时前导零不应该贡献任何值。如果不区分前导零数字 099 会被当成三位数计算时得到 0^2 9^2 9^2 162这和数字 99 的数位平方和 162 碰巧一样所以在“只求最大值”时前导零不影响结果但在某些统计题里前导零会把同一个数重复计数。为了养成好习惯带上 started 更稳妥。3.2 记忆化搜索的代码实现用 Python 写记忆化搜索非常快lru_cache 可以直接缓存函数结果。完整实现如下from functools import lru_cache def max_digit_square_sum_dp(n: int) - int: s str(n) L len(s) lru_cache(None) def dfs(pos: int, tight: bool, started: bool) - int: if pos L: return 0 limit int(s[pos]) if tight else 9 best 0 for d in range(limit 1): next_tight tight and (d limit) next_started started or (d ! 0) cur 0 if next_started: cur d * d best max(best, cur dfs(pos 1, next_tight, next_started)) return best return dfs(0, True, False)这里的逻辑是当前位置枚举数字 d范围由 limit 决定。如果之前已经小于 n那这一位可以随意取 0 到 9如果还在贴着 n那最多只能取到 n 的当前位。next_tight 表示填完 d 之后是否仍然贴着上界。如果 d 已经小于 limit那后面就自由了next_tight 变成 False。在贡献计算上如果 next_started 为 True说明当前位是有效数字贡献 d * d否则还是一个前导零贡献 0。最后取所有分支的最大值。如果题目要求返回最优数字本身而不是最大值可以改造成在 dfs 里记录路径。一个更简单的做法是先算出最大值再从头到尾逐位贪心构造数字。每次枚举当前位置数字 d检查“这一位填 d后面放任取最优”是否等于已经算出的全局最大值如果是就固定 d继续下一位。这个复杂度多一个因子 10但思路很直观。3.3 复杂度分析数位 DP 与候选枚举的对比数位 DP 的状态数取决于 pos、tight、started共 L * 2 * 2 个状态每个状态枚举 0 到 9 共 10 种转移所以总时间复杂度是 O(L * 2 * 2 * 10)也就是 O(L)空间复杂度 O(L)。真正执行时因为 lru_cache 的存在只会访问极少数状态实际运行速度非常快。为了直观对比我把两种解法的复杂度列成一张表方法时间复杂度空间复杂度适用场景暴力枚举O(n * log n)O(1)n 很小仅用于对拍验证候选枚举O(L^2)O(1)只求最大值代码最短数位 DPO(L)O(L)可以扩展额外限制条件这里 L 是 n 的十进制位数。候选枚举虽然理论复杂度是 O(L^2)但 L 不超过 19实际跑起来和 O(L) 没有区别。所以在周赛 Q2 这种简单场景下我优先推荐候选枚举因为它更容易写对而数位 DP 的价值在于通用性当题目改成“数位平方和等于 k 的最大数”或者“第 k 大的数位平方和”时候选枚举会立刻失效数位 DP 的框架还能继续用。4. 比赛中的实战经验与避坑指南4.1 我踩过的三个边界坑第一个坑是把 s[i] 0 时写成 break。我有一个朋友在比赛里就是这么挂的他以为第 i 位是 0 说明后面不可能再产生减一候选但实际遇到 n 100 这种数字答案 162 来自 i 0 的候选“099”。如果第一位不是 0只是后面某一位是 0break 会漏掉更多情况。正确做法永远是 continue让循环走完所有位置。第二个坑是不考虑 n 本身。有些选手构造候选时只枚举“减 1 补 9”忘了把 n 自己放进去。对于 n 199减一补九的候选是 99没减百位和 189减十位以及 198减个位它们的数位平方和分别是 162、146、194算一下198 是 1 81 64 146189 是 1 64 81 14699 是 162而 199 本身是 1 81 81 163比所有减一候选都大。所以 n 本身必须作为候选之一参与比较。第三个坑是在数位 DP 里忘了传 tight。代码写多了容易出现一个惯性错误只在开头用 limit 判断却忘记把下一个状态的 next_tight 更新。一旦漏掉结果会把大于 n 的数也纳入候选比如 n 50 时可能算出 99 的数位平方和 162这显然是错的。写 DP 的时候每一步都要把“当前是否贴住上界”这个状态传递下去。4.2 候选枚举和数位 DP 怎么快速选择我自己的判断标准很简单如果题目只要求最大值且没有别的约束条件直接候选枚举因为代码量最少不容易出错。如果题目附加了“恰好等于某个数”“余数等于多少”“要求输出最优数本身”之类的条件或者 n 的长度可能达到 100 位大数场景就老老实实写数位 DP。补充一个技巧在比赛环境中如果时间充裕我建议把暴力解法和优化解法同时写出来用小数据做对拍。虽然 LeetCode 上不能直接对拍但本地写一个随机数据脚本验证两个函数结果一致能显著提高 AC 概率。尤其对于这种结论型贪心对拍可以发现一些边缘的形态判断错误。4.3 双周赛做题节奏与相关题目扩展双周赛的前两题通常要求 20 分钟内解决。Q1 基本是模拟题Q2 开始有一点算法含量但不会太难。遇到数位平方和这类题第一步永远是看数据范围一旦发现 n 很大暴力直接出局接下来再观察目标函数的结构。平方和的凸性是一个非常强的提示它引导你思考“9 的收益最大化”。如果你能在 2 分钟内想到候选枚举这题就是送分题。这类题目还可以继续扩展。比如力扣 202 题“快乐数”用的是完全相同的数位平方和定义但是不同的过程258 题“各位相加”则变成了数位和有一些 Codeforces 题目会要求你把数字替换成数位平方和并重复 k 次需要快速幂思想。这些题本质上都在考同一个能力对数位结构的观察。练好这一道再去做这些题会轻松很多。如果赛场上真的卡在 Q2我有个小习惯先写暴力和优化版对拍如果优化版在小数据上全过就大胆提交如果 WA 了优先检查边界值比如 n 0、n 9、n 10、n 99、n 100、n 109。这些数字专门用来验证“借位”和“前导零”问题是这套代码最容易出错的地方。最后再分享一个经验不要小看这种 Q2 小题。它背后涉及的贪心论证、数位 DP 框架、边界处理正是双周赛 Q3、Q4 的常见前置知识。我认识很多选手在 Q3 卡住回头看才发现是 Q2 里的某个概念没有真正吃透。把这道题按照本文思路完整写一遍再把候选枚举和数位 DP 两种写法都跑通以后遇到再复杂的数位问题心里都有底。
