第 168 场双周赛的 Q2，题目编号 3723，名字叫“数位平方和的最大值”。这道题我在比赛时花了 8 分钟 AC，属于典型的“看着像难题、实际有套路”的送分题。很多选手卡住是因为一开始就想着暴力枚举，看到 n 的范围直接懵了；但只要把“平方和”和“不超过 n”这两个条件拆开看，解法非常清晰。本文我会从暴力解法讲起，逐步推导出两个可 AC 的方案：候选数枚举和数位 DP，再把比赛现场容易踩的边界坑全部列出来，适合正在刷双周赛、准备突破 Q2 的选手参考。
1. 题目解读：数位平方和到底在求什么
1.1 数位平方和的定义
先统一概念。给定一个非负整数 x，把它拆成十进制位，每一位平方后再求和，就是数位平方和。比如 x = 123，数位平方和是 1^2 + 2^2 + 3^2 = 14；x = 99，数位平方和是 81 + 81 = 162；x = 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^9，Python 要跑十亿次循环，每次还有内层取位操作，整体耗时几十秒，比赛环境直接超时。如果把 n 上升到 10^18，这就不是慢几倍的问题，而是彻底不可行。
所以本题真正要解决的核心问题不是“怎么算数位平方和”，而是“如何跳过大量无用的数，只考察极少数候选数字”。大多数人对“数位 DP”这个词有心理负担，其实这道题根本不需要先上数位 DP，有一个更简单的贪心构造方法，30 行代码就能写完。
1.3 先建立直觉：答案长什么样
我先举几个例子找感觉。n = 19 时，0 到 19 里所有数的数位平方和如下：19 本身是 1 + 81 = 82，18 是 1 + 64 = 65，17 是 50，9 是 81。最大是 82，对应的就是 n 本身。再看 n = 100：100 自己的数位平方和是 1，而 99 的数位平方和是 81 + 81 = 162，显然 162 更大。再看 n = 200：200 自己是 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 = 64，10^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 # 候选 1：n 本身 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 的前缀相等（tight=True）或已经小于 n（tight=False），以及此前是否已经填过一个非零数字。函数返回值是从第 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) | 只求最大值，代码最短 |
| 数位 DP | O(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，只是后面某一位是 0，break 会漏掉更多情况。正确做法永远是 continue，让循环走完所有位置。
第二个坑是不考虑 n 本身。有些选手构造候选时只枚举“减 1 补 9”，忘了把 n 自己放进去。对于 n = 199，减一补九的候选是 99（没减百位）和 189（减十位）以及 198（减个位），它们的数位平方和分别是 162、146、194？算一下：198 是 1 + 81 + 64 = 146；189 是 1 + 64 + 81 = 146；99 是 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 两种写法都跑通，以后遇到再复杂的数位问题心里都有底。
