最近重新刷到“完全平方数”这道题它在我自己整理的刷题清单里排在第84道。说实话第一次看到这个题目名字的时候我觉得它是个纯粹的数学题结果看了三分钟就动手写了段暴力枚举的代码然后在一个很小的样例上就发现不对劲。后来才明白这道题表面上在问“最少需要几个完全平方数”实际上是在考两件事你能不能把“凑数”问题抽象成动态规划以及你能不能想到把它当成一张图来跑最短路。无论你是刚开始准备算法面试还是已经刷了一段时间想巩固模型思维这道题都值得花一个小时彻底吃透。这篇文章会把三种主流解法、对应的完整代码、复杂度对比和调试经验一次性讲清楚。1. 题目拆解它到底在考什么1.1 先看题目本身题目给一个正整数 n要求用若干个完全平方数1、4、9、16……的和来表示它问最少用几个。例如 n12可以拆成 444答案是3n13可以拆成 94答案是2。n 从1开始答案至少是1最坏情况下可以全部拆成1所以答案不会超过 n。这里有两个容易被忽略的细节第一每个平方数可以使用多次没有次数限制第二只要求返回“最少个数”不要求输出具体拆法。很多人在这个细节上栽过跟头——想太多把简单问题想复杂了。其实第二个细节决定了做法可以非常直接我们不需要记录具体路径只需要记录“达到每个数字最少需要几步”。1.2 为什么“先选大平方数”会翻车很多人第一反应是贪心尽量先把最大的平方数拿出来。比如 n12 时最大的平方数是9剩下3只能拆成111总共4个但最优解是444只要3个。换句话说贪心在这个例子上直接失效。再举一个更极端的例子n18贪心会先拿16剩下2拆成11总共3个可实际上 1899答案是2。为什么贪心总是出错因为平方数之间不存在“整除”或“倍数”关系占的块头大不代表后续剩余部分容易处理。局部最优拼不出全局最优这是组合优化里最常见的陷阱。题目真正要逼迫你做的是放弃“挑选最大”的思路转向“枚举所有可能的结构”。1.3 问题本质一个换零钱的模型把平方数当作硬币面额1、4、9、16……n 就是要凑的目标金额每种硬币无限使用问最少用几枚硬币凑齐。这就是经典的“零钱兑换”模型只不过硬币面额不是由输入给出的而是由“完全平方数”这个条件生成的。一旦完成这个转化解法就框架化了“最少”暗示最优子结构“组合”暗示状态枚举无限次使用和完全背包同源。这题其实就是穿着“平方数”马甲的零钱兑换。正因如此它成为很多刷题玩家从“会做一题”到“会做一类题”的转折点。2. 动态规划解法最稳的入门路线2.1 状态设计和转移方程是怎么来的先说结论用 dp[i] 表示“整数 i 至少需要多少个完全平方数”。如何推导转移方程核心技巧是关注“最后一个平方数”。假设凑出 i 的方案里最后一个平方数是 jj那么去掉它之后剩下的部分就是 i-jj所需个数是 dp[i-jj]。再加上这一个 jj就得到一种候选答案 dp[i-jj] 1。由于最后一个平方数可能是 1、4、9……所以要遍历所有满足 jj i 的 j取最小值。这里有一个值得讲透的“为什么”一个方案里的平方数是无序的但无论你把哪个平方数放在最后在枚举时它都会被覆盖到所以不会漏解因为所有 j 都遍历了所以取到的一定是全局最小值不会受到顺序干扰。子问题 dp[i-j*j] 的规模比 i 小天然满足无后效性。这其实就是动态规划最核心的两个条件最优子结构 无后效性。2.2 完整代码与运行逻辑def numSquares(n: int) - int: dp [0] * (n 1) for i in range(1, n 1): dp[i] i # 最差情况全部由 1 组成 j 1 while j * j i: dp[i] min(dp[i], dp[i - j * j] 1) j 1 return dp[n]这段代码读起来很直白外层从小到大算每个数的答案内层枚举每一种“最后一个平方数”。初始化 dp[i] i相当于先假设全部由1组成然后内层不断用更小的候选值去覆盖。dp[0]0 是关键底座当 i 本身就是完全平方数时dp[i-j*j] 就是 dp[0]加1后等于1正确反映“一个平方数就够”。最后返回 dp[n]。如果想再快一点可以在进入内层之前先判断 i 是不是完全平方数是就直接把 dp[i] 设为1并跳过内层循环。不过我建议刚开始学的时候不要加这个优化先把朴素内层循环吃透。这段代码在 n10^4 时运行非常快在 n10^6 以上会明显变慢需要换思路。2.3 复杂度数据与两个关键边界时间复杂度是 O(n√n)外层 n 次内层最多 √i 次累加得到 ∑√i ≈ n√n。空间复杂度 O(n)。这组数据意味着n ≤ 10^5 时 DP 很稳n 到 10^7 时操作次数超过十亿基本跑不动必须寻找数学解法。两个关键边界值得记在小本子上。第一dp[0] 必须为0否则所有本身就是平方数的数字都会错误加1。第二内层条件的边界是 jj i 而不是 jj i写错会漏掉“本身就是平方数”的转移。另外如果使用 C 这类强类型语言当 n 接近 10^9 时jj 用 int 会溢出建议写成 j n / j或者用 long long 暂存 jj。3. BFS解法换个角度就是最短路3.1 把“减平方数”看成走图BFS 的思路有两种理解方式。一种是“反向做减法”从 n 出发每次减掉一个完全平方数得到一个新数字目标是减到0那么“减的次数”就是答案。例如 n13先减9得到4再减4得到0两步完成对应 1394。另一种理解是倒过来“从0做加法”但在实现上减法更自然。在这个模型里数字是节点“从一个数字减掉一个平方数到达另一个数字”是边每条边的代价都是1。于是问题变成n 到 0 的最短路径长度。无权图求最短路BFS 是按层扩展的第一次到达0时的步数就一定是最小步数。这背后的逻辑是BFS 保证“先到达的路径长度不超过后到达的路径长度”所以一旦命中0直接返回即可不需要继续扩展。3.2 完整实现与剪枝细节from collections import deque def numSquares(n: int) - int: q deque() q.append((n, 0)) visited set() visited.add(n) while q: cur, step q.popleft() if cur 0: return step j 1 while j * j cur: nxt cur - j * j if nxt not in visited: visited.add(nxt) q.append((nxt, step 1)) j 1 return -1这个实现里有三个细节必须说清楚。第一visited 集合是必须的如果不剪枝同一个数字会从不同路径反复入队n100 时就可能出现上千次重复访问n稍大直接超时。第二队列元素用 (cur, step) 携带步数也可以用分层 BFS 的方式记录层号本质上没有区别。第三当 cur 本身就是0时弹出后第一件事就是返回 step这个判断放在最前面。从扩展效率上说每个节点最多被访问一次每次访问要枚举最多 √cur 个平方数所以最坏复杂度也是 O(n√n)。但因为 BFS 一旦命中0就停止很多情况下实际运行比 DP 快尤其是答案很小比如2或3的测试数据。3.3 DP和BFS怎么选面试场景下我的建议是优先 DP它思路最直接代码也短不容易被追问细节。BFS 可以作为“换模型”的加分项因为它展示了你对图的抽象能力。实际工程中如果 n 规模较小二者都行如果答案大体上都很小BFS 的提前退出机制通常更快如果系统要求稳定的最坏复杂度DP 更可控。我个人的刷题习惯是先默写 DP再用 BFS 验证答案最后用数学解压轴检查。三道解法互相印证基本不会出现结果对不上的情况。4. 数学优化四平方和定理直接出答案4.1 先记住一条数论经典结论四平方和定理说任意正整数都可以表示为至多4个整数的平方之和。注意是“至多4个”所以这道题的答案只有四种可能1、2、3、4。这个结论直接把一个搜索问题变成了判定问题。但只知道“至多4个”还不够因为这四种情况分别对应什么条件才是解题的关键。更细的结论是三平方和定理一个正整数可以表示为3个整数的平方之和当且仅当它不形如 4^k(8m7)。换句话说凡是形如 4^k(8m7) 的数必须用4个平方数才能表示。这两条结论合起来就给了我们完整的判定路径。4.2 判定答案的完整流程判定顺序可以这样设计如果 n 本身就是完全平方数返回1。把 n 里的因子4全部约掉得到 t判断 t 是否满足 t ≡ 7 (mod 8)若满足返回4。枚举 a 从1到√n看 n - a^2 是否是完全平方数若存在返回2。走到这里说明既不是1也不是2也不可能是4直接返回3。对应的代码def is_square(x: int) - bool: r int(x**0.5) return r * r x def numSquares(n: int) - int: if is_square(n): return 1 t n while t % 4 0: t // 4 if t % 8 7: return 4 a 1 while a * a n: if is_square(n - a * a): return 2 a 1 return 3时间上主要是枚举 a 的循环最多 √n 次所以复杂度 O(√n)空间 O(1)。在 n 达到 10^9 甚至更大时这套逻辑依然毫秒级返回。4.3 一个容易翻车的细节和复杂度对比最容易翻车的是第二步很多人直接判断 n % 8 7没有先把4的因子约干净结果把 8 判断成“必须用4个平方数”。实际上 8 4 4答案只有2。原因在于结论里的指数 k 是任意的非负整数而不仅仅是0所以要先循环除以4。另一个容易忽略的点第二步判断的是“不能表示成3个平方数之和”所以如果命中这个条件答案既不是1也不是2也不是3只能是4如果没有命中且枚举后发现无法拆成两个平方数则答案是3。解法核心思想时间复杂度空间复杂度适用规模动态规划状态转移枚举最后一个平方数O(n√n)O(n)n ≤ 10^5BFS数字作为节点求最短路径O(n√n)O(n)n ≤ 10^5答案小更快数学判定四平方和定理定性O(√n)O(1)任意规模对比之后结论很清楚刷题平台上数据规模通常 n ≤ 10^4 或 10^5DP 完全够用但在一些变体题里n 可能很大或者面试官要求“不许用数学结论”这时候就要靠建模能力而不是背结论了。5. 常见问题与排查技巧实录5.1 DP数组初始化错位的排查实际写代码时最常见的错误是 dp[n] 返回一个比正确答案大1的值或者是一个接近 n1 的怪值。原因通常是 dp[0] 没定义好。比如把 dp[0] 初始化为一个很大的数那么当 i 是完全平方数时dp[i] min(dp[i], dp[i-j*j]1) 会变成 min(i, 大数1) i结果等于没有利用这个平方数答案自然偏大。排查方法很简单手动跑 n4打印 dp[0] 到 dp[4]看 dp[4] 是否等于1如果等于4问题几乎一定出在 dp[0] 或内层边界 j*j i 上。不要嫌打印日志麻烦这种小问题靠肉眼盯代码经常盯不出来一打印就能定位。5.2 BFS超时的一般检查顺序如果你写的 BFS 超时按以下顺序排查是否在最开始把起点加入 visited如果漏了起点会被重复处理。是否在每层都重复计算平方数更优做法是先用循环生成不超过 n 的平方数列表再在扩展时遍历这个列表。是否用 set 记录大量整数Python 里 set 查找很快但内存开销大如果只是验证思路也可以先用一个布尔型数组记录n 小的时候更省。是否没有提前终止BFS 应该在第一次 pop 出0时立即返回不要等队列清空。一般情况下这四步改完超时问题就解决了。尤其是第四点很多人惯性把 BFS 写成遍历完整张图反而把难度从“最短路”变成了“全图搜索”。5.3 手算核对用的测试用例表纯靠感觉写代码很容易在边角出错。下面这组用例可以直接手算核对覆盖了1到4四种答案n预期答案一种可行拆法111221133111414524174411182441234441329418299234164112841644431425411验证的时候可以先用 DP 跑一遍再用数学解跑一遍两个结果一致基本就稳了。如果只有一两个用例不一致优先怀疑是不是完全平方数本身被漏判了。5.4 现场调试的一个小故事我印象很深的一次调试是一个同学写出了 DP前几个用例全对但 n8 时输出4而不是2。我们把 dp 数组打出来发现 dp[4]4dp[7]4问题都出在“4”没有正确识别为完全平方数。原因是他写的是 j * j i 而不是 j * j i所以当 i4 时内层最多只试到 j1永远等不到 j2 的那次转移。这看起来是个极小的符号错误却完美覆盖了所有“本身就是平方数”的数字。后来我把这种错误总结成一句话边界条件不是靠背的是靠“拿平方数本身去验算”发现的。从那以后我每次写完 DP 都会先跑 n 为平方数的用例这个习惯帮我省下了不少时间。6. 从这道题延伸出去的通用能力6.1 它和“零钱兑换”“最短路”的共性“完全平方数”并不是一道孤立的题。把平方数换成任意硬币面额就是零钱兑换把“减去平方数”换成“走到相邻格子”就是网格最短路把数论结论抽掉你就拥有了解决一大类“最少组合数”问题的通用武器。以后看到“最少需要几步”“最少要多少个”“最少凑成”这类关键词第一反应应该是能不能定义 dp 状态能不能建模成图这两个问题问完一半的题已经解完了。如果答案是“能”再根据数据范围决定用 DP 还是 BFS这就是刷题从“背答案”到“掌握方法论”的分水岭。6.2 不同数据规模下的真实体感我做过一个不算严谨的小实验n 取 9999 时DP 几乎是瞬间出结果BFS 因为答案只有4也很快n 取 99999999 时DP 在常规环境下已经很难跑完BFS 也明显吃力而数学解依然是瞬间返回。这个体感让我对“复杂度分析”有了具象认识O(n√n) 和 O(√n) 的差距不是常数级别的差距而是能否应对大规模数据的问题。刷题时如果不关注数据范围再正确的算法也可能在一次超大测试上翻车。现在每逢做这类题我都会先看约束条件里 n 的最大值再决定要不要上数学解法。6.3 给后续刷题者的建议如果这道题你是第一次见建议按这个顺序练先手推小样例理解贪心为什么错再默写一遍 DP不看答案把 BFS 写出来最后再了解数学解。每一步停留的时间不要短于“自己能把为什么讲清楚”。等到你可以在五分钟内从 DP 推导到 BFS、再用数学解验证结果时这道题才算真正吃透了。我自己的习惯是把这类“一题三解”的题目单独收集在一起反复重刷因为它们的价值不在题目本身而在帮你建立不同算法思路之间的连接。刷完这一道你会发现以后再遇到类似的题已经不再是“没做过”的状态而是能下意识地往正确的方向想。