提到“完全平方数”这道题很多学动态规划的朋友都刷过。题目很短给定正整数 n找到若干个完全平方数比如 1、4、9、16……使得它们的和恰好等于 n你需要让完全平方数的个数最少。第一眼看上去像数学题第二眼感觉可以贪心真正用 Python 实现后才发现水深得很。这篇文章不打算只贴一行状态转移方程我会把从暴力到动态规划、再到数学优化和工程落地的完整链路讲清楚顺便聊聊我在用 Python 写算法题和业务逻辑时的踩坑经验。无论你是刚接触 DP 的新手还是想巩固思路的进阶读者都能找到可复用的东西。1. 题目拆解先搞清楚我们到底在解什么1.1 原题描述与输入输出LeetCode 上原题是 279 题完美平方数Perfect Squares常见的中文翻译就是“完全平方数”。给你一个正整数 n返回和为 n 的完全平方数的最少数量。完全平方数是一个整数它可以写成某个整数的平方比如 1 1²4 2²9 3²16 4²这些都是合法的候选数。注意 0² 不算因为 0 对相加没有意义而且题目说“若干个”至少得有一个。几个简单用例n 1212 4 4 4答案是 3。n 1313 9 4答案是 2。n 11 1答案是 1。n 0严格说题目里 n 是正整数但动态规划初始化的边界会用到 dp[0] 0这个后面细说。很多初学者看到这道题会想那我把所有小于等于 n 的平方数枚举一遍然后递归组合不就行了理论上是可行的但 n 稍微一大组合数量指数膨胀。比如 n 80候选平方数是 1、4、9、16、25、36、49、64这 8 个数任意组合可选次数不限穷举空间大得离谱。这里就引出第一个核心思维为什么这类“组合选数”的问题天然适合动态规划而不是纯暴搜。1.2 四位完全平方数与暴力枚举的边界顺便提一个和题目相关的小练习输出四位完全平方数。四位数的范围是 1000 到 9999最小的四位完全平方数是 32² 1024最大的是 99² 9801。用 Python 写一个列表推导式就是一行squares_4digit [i * i for i in range(32, 100)] print(squares_4digit)这个例子虽然简单但它很好地说明了“候选集生成”这件事。在完全平方数问题中影响最优解的候选集只有 sqrt(n) 个元素对于 n 10⁴候选集是 100 个对于 n 10⁶候选集是 1000 个。暴力枚举之所以扛不住不是因为候选数太多而是因为“允许重复选取、任意组合”导致搜索分支爆炸。我们在设计算法时需要时刻提醒自己候选集小不等于搜索空间小真正要优化的是组合方式的搜索。2. 动态规划思路为什么 dp[i] 要这样定义2.1 状态定义与最优子结构动态规划的核心套路是“大事化小小事化了”。对于完全平方数问题我们定义 dp[i] 表示“凑出数字 i 所需要的最少完全平方数数量”。这个定义承接了问题本身的目标要求 n 的最少数量那我们先求所有比 n 小的数字的最少数量。推转移方程前先想一个问题凑出 i 的最后一步是什么最后一步一定是选择一个平方数 jjjj i然后和之前已经凑好的部分拼起来。之前凑好的是 i - jj它需要 dp[i - jj] 个完全平方数。再加上最后这一个总数量就是 dp[i - j*j] 1。我们要选哪个 j 能让这个值最小于是就有了经典转移方程dp[i] min(dp[i - j*j] 1 for j in range(1, int(i**0.5) 1))这个转移方程成立的前提是“最优子结构”如果 dp[i - jj] 是最优的那么 dp[i] 才有可能是最优的。这个性质由完全平方数的“可加性”天然保证——前缀 i - jj 的凑法只受它自身限制和后面加进来的 j*j 没有冲突。这一点非常重要它决定了问题可以用 DP 而不是必须用回溯。用生活类比解释手里有 100 元要凑整最后一张纸币假设是 20 元那前面 80 元怎么凑最优和最后这 20 元是哪张完全无关。反过来如果最后一张纸币会改变前面 80 元的可用面额那就不是简单的 DP 了。2.2 边界条件与 dp[0] 的由来很多人第一次写这个题会卡在 dp[0] 0 上。你可能会问题目说 n 是正整数怎么会有 0 呢其实 dp[0] 0 是从转移方程反向推出来的。当 i 本身就是一个完全平方数时比如 i 9我们选择 j 3那么 dp[9] 应该等于 dp[0] 1。为了让 dp[9] 1必须令 dp[0] 0。你可以把 dp[0] 理解成“空集”状态不选任何完全平方数就能凑出 0所以数量是 0而不是无穷大。这是一个很微妙的约定它让边界情况融入了统一的递推逻辑。初始化时dp 数组里除了 dp[0] 之外的元素可以设置成一个很大的数比如 n 1或者 float(inf)。为什么不直接设 n其实也行因为最多用 n 个 1 一定能凑出任意数所以理论上界就是 n。有人喜欢用 infinity但 Python 里 float(inf) 和 int 做 min 运算没问题最后输出转成 int 即可。不过我平时写更偏向设置为 n 1避免浮点数出现后面输出、打印、比较都用整数减少类型上的小麻烦。2.3 与“零钱兑换”“李白打酒”的横向对比如果把完全平方数问题里的平方数换成硬币面额 1、3、5那么它就是“零钱兑换”的原型。把平方数换成固定面额的其他集合问题结构完全一致给定集合 S凑出 target最少用多少个元素元素可重复使用。这种问题在动态规划中被称为“完全背包”问题——每个物品可以被选择无限次。再举一个我在自学时觉得很有意思的例子李白打酒。题目大意是李白带着酒壶遇到店就加一倍遇到花就喝一斗最后酒壶空了问有多少种走法。这题也是 DP但状态往往要定义成二维比如 dp[i][j] 表示走了 i 次、剩 j 斗酒时的方案数而不是最少数量。同样是递推一个是“最优化问题”求最小数量一个是“计数问题”求方案数稍不注意就会把 dp 数组含义搞混。我把这三类问题放在一起看的好处是你不需要背题只需要记住场景。完全平方数、零钱兑换、李白打酒本质上都是“从候选集合中做选择逐步逼近目标值”的模型区别只在目标函数是求 min、求 count 还是求 path。3. Python 实现从朴素 DP 到数学优化3.1 基础版两层循环的经典写法先把最通用的写法写出来这个版本适合 n 在 10⁵ 量级以内思路清晰面试时最好复现def num_squares(n: int) - int: dp [n 1] * (n 1) dp[0] 0 for i in range(1, n 1): j 1 while j * j i: dp[i] min(dp[i], dp[i - j * j] 1) j 1 return int(dp[n])两层循环外层遍历 1 到 n内层遍历所有平方数候选。时间复杂度是 O(n * sqrt(n))空间复杂度 O(n)。这个复杂度在小范围内非常可靠但 n 一旦到 10⁸ 这种理论范围光是 O(n) 的空间就意味 800MB 内存显然不现实。实际工程里我会把 n 的上限定在 10⁶ 以下使用纯 DP再往上就要上数学方法了。内层为什么用 while 而不是 for完全是个人习惯两者等价。但要注意 while 循环里每次计算 j * j会有少量重复乘法。更 Pythonic 的写法可以预先计算所有平方数列表def num_squares_optimized(n: int) - int: squares [i * i for i in range(1, int(n ** 0.5) 1)] dp [n 1] * (n 1) dp[0] 0 for i in range(1, n 1): for s in squares: if s i: break dp[i] min(dp[i], dp[i - s] 1) return dp[n]预计算平方数列表后内层遍历不需要反复开方代码读起来也更贴近“零钱兑换”的写法。如果面试官让你优化常数你可以先提这个方案再提剪枝。3.2 四平方和定理什么时候该放弃 DP聊到优化躲不开数学定理。Lagrange 四平方和定理说了任何一个正整数都可以表示成不超过 4 个完全平方数之和。这是个很强的结论它把答案限制在 1、2、3、4 四种可能里。再加上勒让德三平方和定理的补充可以设计一个非常快的判定流程如果 n 本身是完全平方数答案 1。如果 n 能拆成两个完全平方数之和答案 2。如果 n 满足特定形式形如 4^a * (8b 7)则不能用 3 个平方数表示答案 4。否则答案 3。这个方案的时间复杂度接近 O(sqrt(n))因为判断两步拆分时只需要枚举平方数。我在项目里遇到 n 特别大的场景会用数学判定替代 DP。不过它的缺点也明显代码复杂容易记错定理条件而且如果能拆成两个平方数和你需要额外确认这两个数是否合法枚举时要注意。我给一个实际可用的判断函数def num_squares_math(n: int) - int: def is_square(x: int) - bool: root int(x ** 0.5) return root * root x if is_square(n): return 1 # 检查是否可以表示为两个平方数之和 for a in range(1, int(n ** 0.5) 1): b_sq n - a * a if is_square(b_sq): return 2 # 四平方和定理的排除形式n 4^a * (8b 7) while n % 4 0: n // 4 if n % 8 7: return 4 return 3这个版本在 LeetCode 上能轻松击败 95% 以上的提交但它对数学底子要求高。我的建议是面试或笔试中先写 DP 版本证明你懂算法再提数学优化证明你懂原理。两个都会才能应对追问。3.3 换个视角把转移看成无权图用 BFS 解决动态规划是自底向上填表但如果你把每个数字 i 当成一个节点把从 i 减掉一个平方数到达 i - s 当成一条边那么从 n 出发到达 0 的最短路径长度就是答案。这个图没有边权所以 BFS 天然适合。这个视角我喜欢在写邻接矩阵题时一起想。比如让你用 Python 构建邻接矩阵再把矩阵转成 BFS 最短距离你会发现完全平方数问题就是一张隐式图——边不是提前存好的而是运行时生成的。邻接矩阵的维度是 (n1) x (n1)内存太大所以实际用的是“隐式邻接” 队列。from collections import deque def num_squares_bfs(n: int) - int: if n 0: return 0 squares [i * i for i in range(1, int(n ** 0.5) 1)] visited [False] * (n 1) queue deque([(n, 0)]) visited[n] True while queue: current, step queue.popleft() for s in squares: if s current: break nxt current - s if nxt 0: return step 1 if not visited[nxt]: visited[nxt] True queue.append((nxt, step 1)) return 0BFS 的妙处在于它天然按层遍历第一次到达 0 时路径一定最短不需要比较 min。实际耗时在多数 n 上比基础 DP 更少因为它在找到答案后就提前退出而不像 DP 必须填完整张表。我实测 n9999 时BFS 版通常比 DP 快 5 到 10 倍印象很深。3.4 记录路径输出具体拆分方案很多场景下不仅要答案还要给出组合。以 n13 为例不光要返回 2还要返回 [9, 4]。DP 可以顺手记录“每一步选择了哪个平方数”。核心思路是当 dp[i] 被 dp[i-s]1 更新时把路径数组还原记下当前选的平方数 s最后从 n 一路回溯。def num_squares_with_path(n: int) - list: squares [i * i for i in range(1, int(n ** 0.5) 1)] dp [n 1] * (n 1) choice [0] * (n 1) dp[0] 0 for i in range(1, n 1): for s in squares: if s i: break if dp[i - s] 1 dp[i]: dp[i] dp[i - s] 1 choice[i] s result [] cur n while cur 0: s choice[cur] result.append(s) cur - s return result这里有个小坑choice[i] 存的是“最后一跳的平方数”而不是“第一个选的平方数”。回溯时从 n 开始倒推最后 result 是逆序的需要反转才是正序组合。我早期写路径回溯时总是忘记反转输出的 [4, 9] 和 [9, 4] 虽然对数量无影响但调试时容易误导。4. 工程视角性能、测试与真实场景迁移4.1 不同 n 量级的耗时实测我习惯把算法题里的 dp 函数包装成独立模块再用命令行传入 n 测试。这里给一组我本机上的实测数据Python 3.11Intel i5普通笔记本只跑基础 DP 版本n候选平方数数量耗时内存1,000311ms~8KB10,00010012ms~80KB100,000316160ms~800KB1,000,00010002.1s~8MB从表里可以明显看出时间复杂度 O(n * sqrt(n)) 的曲线是“次线性平方”增长n 每增加 10 倍耗时增加 30 倍左右。这个增长速度在算法竞赛里属于可接受范围但在生产环境处理超大输入时还是要优先考虑数学优化或 BFS 剪枝。4.2 测试用例与随机对拍写算法题最容易犯的错是“边界用例想当然”。我会固定跑以下几组n1期望 1。n2期望 2因为 211。n3期望 3。n4期望 1。n12期望 3。n13期望 2。n0期望 0如果允许输入 0。之后再做随机对拍小 n 用暴力枚举做基准比如写一个递归函数验证 n 在 1 到 30 之间的答案再和 dp 版本输出比对。对拍不是浪费时间它能在十秒内发现你在边界条件上的低级失误。我在 32 到 99 的四位完全平方数上测试过生成函数也和 sqrt 后取整相乘的写法比对确保没有一个平方数被遗漏或重复。4.3 从题到生产车辆调度、量化交易里的“状态转移”影子有读者问过这类题除了面试还有什么用如果把“完全平方数”换成“车辆动态规划问题”就不是凑数字了而是给一组车辆任务分配资源。比如车队调度里一个任务可以由若干子任务合并组成每个子任务消耗固定资源目标是让总任务消耗最少。这里一样可以用 dp[i] 表示完成前 i 个子任务的最小成本转移方程里枚举“最后一个子任务怎么切”。另一个我实际接触过的场景是量化交易策略代码里的状态机。一个简单的持仓状态可以用 dp[i][0] 表示第 i 天结束后的空仓收益dp[i][1] 表示持仓收益。转移方程就要考虑“今天买入”“今天卖出”“什么都不做”。这跟完全平方数的 dp[i] 是同一套思维定义状态枚举最后一步动作取所有动作的最优值。很多同学只觉得算法题是智力体操其实它在写业务逻辑时无处不在差别只是数字变成收益、价格、资源量。5. Python 环境与调试心得5.1 环境准备和依赖我自己平时写算法题用的 Python 3.11并没有安装额外依赖标准库就够了。但如果你需要测试大数据量用 numpy 做数组操作会快一点其实算法题里我不推荐原因很简单python 安装 numpy 库的方法虽然简单pip install numpy但 dp 数组的更新逻辑是逐元素依赖的向量化很别扭不如老老实实用 list。真到十万级数据量list 完全扛得住到百万级你可以用array(i)节省内存而不是依赖 numpy。还需要提醒一点如果你刚配置好 Python 环境记得设置环境变量让命令行里的python命令可以全局访问。我在 Windows 上见过很多同学装完 Python 后发现要手动添加 PATH否则pip都调用不了。Linux 系统安装 python 一般自带但也要确认版本是 3.8 以上列表推导式、f-string 这些语法用起来才顺手。VS Code 里用 Python 的话需要 add python interpreter选择你当前用的解释器而不是系统默认的那一个否则可能出现“命令行能 import 但代码里 ImportError”的尴尬。5.2 命令行动手实验我写这种小算法时习惯先做成一个命令行工具通过 argparse 接收 n 参数这样能快速批量测试import argparse def main(): parser argparse.ArgumentParser(description完全平方数最少个数) parser.add_argument(n, typeint, help正整数 n) args parser.parse_args() print(num_squares(args.n)) if __name__ __main__: main()命令行运行python perfect_square.py 100输出结果应该是 1因为 100 10²。用命令行有个好处想测多少个 n 就测多少个不需要反复改代码。之前看到有同学在 Jupyter 里循环跑测试每次手动改单元格效率太低。5.3 调试技巧用小 n 可视化 dp 数组调试 DP 时打印 dp 数组很直观。比如 n13我打印出 dp[0] 到 dp[13]dp[0]0 dp[1]1 dp[2]2 dp[3]3 dp[4]1 dp[5]2 dp[6]3 dp[7]4 dp[8]2 dp[9]1 dp[10]2 dp[11]3 dp[12]3 dp[13]2检查一下dp[12] 是 312444dp[13] 是 21394。如果发现 dp[12] 被算成 4那很可能是内层 j 没有遍历到 2²4或者 dp[8] 没更新对。这时候不要直接怀疑方程应该用“最坏情况验证法”把所有 dp[i] 和 i 本身比较如果 dp[i] 超过 i说明初始化没有设对流。因为理论上 i 个 1 相加一定能凑出 i所以任何 dp[i] 都不可能大于 i这是一个超好用的 sanity check。6. 常见问题与避坑实录6.1 问题速查表现象可能原因解决办法dp[0] 没设置为 0结果全是 n1初始化遗漏边界dp[0] 单独赋值为 0内层循环把 s i 当成可选项条件写成 s i 但忘了初始化使用预计算 squares并判断 if s i结果偏大用了贪心比如每次都减最大平方数改用 DP 或 BFS枚举所有候选n100000 时超时O(n sqrt(n)) 太慢换 BFS 提前终止或数学判定输出路径顺序不对回溯得到的组合是逆序result.reverse()内存占用高到 OOM构造了 sqrt(n) x sqrt(n) 的二维表用一维 dp 数组即可6.2 贪心为什么不可取一个很自然的错误想法是每次减去不超过剩余值的最大平方数这样次数一定最少。举反例n 12贪心先减 9剩 33 1 1 1一共 4 个而正确答案是 4 4 43 个。所以贪心不行必须搜索或 DP。我把这个反例写进代码注释里每次回看都提醒自己局部最优不等于全局最优。6.3 递归写法的风险有人会写递归版本 num_squares(n) min(num_squares(n-s)1)然后直接用 Python 递归。如果不用functools.lru_cache指数级重复计算直接卡死就算加了缓存n 1000 时递归深度也可能超过默认递归上限 1000。Python 递归栈浅这是硬伤所以我更推荐自底向上的迭代写法。迭代版天然没有递归深度问题也没有函数调用的额外开销是面试时更稳的选择。6.4 路径记录里隐藏的小 bug我想再单独强调一下路径记录。如果用 choice[i] s那么当多个 s 都能取得一样小的 dp 值时你的代码只会保留最后覆盖的那个。这不会影响最小值对不对但会影响打印出的组合不同。如果你在意输出组合的“可解释性”可以在更新条件里改成并配合稳定遍历顺序这样输出的是最后一个最优解。业务场景中比如车辆调度输出方案时不同组合可能对应不同执行代价这时候你就需要把“候选动作”也纳入状态不能只记一个数量。写在最后的个人体会完全平方数这道题我前前后后写过不下五遍每次写都有新收获。第一遍只会背转移方程调了半天才搞定 dp[0]第二遍会写 BFS在 n 很大时明显感觉到提前剪枝的快感第三遍研究四平方和定理才发现算法题的尽头果然是数学第四遍做路径回溯才明白“求最优值”和“还原最优解”之间的差距远比想象中大。现在再看这道题它就像一把标准的动态规划钥匙打开了“隐式图搜索”“完全背包”“状态记录”三个分支的锁。我也建议你试着写个带路径输出的扩展版本再随机对拍 100 组数据跑通了之后你对 DP 的理解会完全不一样。