企业官网建设流程全解析

前阵子整理刷题笔记，又看到“完全平方数”这道题，忍不住多说几句。题目并不复杂：给你一个正整数 n，问最少能用多少个完全平方数（比如 1、4、9、16）相加凑出它。12 最少是 3 个，因为 4+4+4；13 最少是 2 个，因为 9+4。如果你刚开始学动态规划，这道题几乎是必刷的入门题；如果你已经刷过一些题，也能从它的数学优化版本里找到新的乐趣。下面我就用 Python 把整个思路掰开揉碎讲清楚，从暴力递归到动态规划，再到数学定理优化，不绕弯子。

1. 先搞清楚什么是最少个数的问题

1.1 题目描述和几个易错用例

完全平方数，简单说就是能写成某个整数平方的数，比如 1、4、9、16、25。题目允许每个完全平方数重复使用，顺序不重要，问的是总个数最少是多少。这不是“有多少种拆法”，也不是“能不能拆”，而是“最少几个”。LeetCode 上这道题的 n 上限一般在一万左右，也就是说用常见的 O(n√n) 动态规划是完全可以接受的。

我习惯先写几个小用例放在脑子里。n=1 的时候答案是 1，因为 1 本身就是完全平方数；n=2 只能是 1+1，答案是 2；n=3 是 1+1+1，答案是 3；n=4 直接一个 4，答案是 1。这些边界看起来简单，但写代码的时候非常容易出错。尤其是 n=3，很多人用公式判断的时候会把它归到“3个平方数”里，却忘了 1+1+1 就是三个，看起来没错，但反过来会影响你对逻辑的判断。

还有一个容易忽略的点：即使某个数本身是完全平方数，也不一定一定要用它。比如 n=12，12 不是完全平方数，你可能会想到 9，但最优解反而用的是 4。这说明“尽量选大的平方数”这种直觉是靠不住的，需要换一种更严谨的思路。

1.2 贪心为什么在这里不成立

我第一次接触这道题，脑子里冒出来的第一个解法就是贪心：每次都选不超过当前剩余值的最大的平方数。拿 13 举例，剩余 13 选 9，剩余 4 选 4，得到 2 个，看起来正确。但一到 12，贪心会先拿 9，剩下 3，只能 1+1+1，加起来 4 个，而真实答案是 3 个（4+4+4）。为什么会这样？因为平方数序列 1、4、9、16、25 之间的间隔不是均匀的，它不像人民币面额那样设计成“贪心一定最优”的结构。

贪心算法的核心假设是“每次局部最好，最终全局就最好”。可在这个问题上，一个看起来很好的“尽量大”的选择，可能把剩余部分推入一个很差的区域。这就像出门赶路，先坐最快的车到某个车站，结果发现那个车站后面全是难走的路，反而慢。你可能会想，那我把所有能减的平方数都试一遍，取最小结果不就行了？对，这就是动态规划要干的事。

1.3 把问题抽象成状态

既然贪心不行，一个个试平方数的话，如果用递归描述，可以写成 f(n) = 1 + min(f(n - j²))，其中 j² ≤ n。这个表达式的含义是：把凑 n 这个任务，看成是“最后一步加了一个平方数 j²，剩下部分继续凑”。于是只要知道 n-j² 的最优解，就能得到一种候选答案。

但这么做有个问题：f(n - j²) 在递归过程中被反复计算很多次，比如 f(10) 可能通过 f(9) 和 f(6) 分别触发一次，层层叠叠，效率很低。真正合适的做法是把这个函数的结果存下来，也就是记忆化搜索；再进一步，干脆从 f(0)、f(1) 开始往大推，这就是动态规划的“自底向上”思路。很多人觉得动态规划玄乎，其实核心就是这个状态函数 f 和它的递推关系。

1.4 从完全平方数到零钱兑换：记住这个模板

这道题看到这里，如果你曾经做过“零钱兑换”，一定会觉得似曾相识。零钱兑换是给你一堆硬币面额，问凑出一个金额最少用几枚；完全平方数相当于把“硬币面额”换成了所有平方数，并且每个面额不限使用次数。两者的状态定义、转移方程、初值设定几乎一模一样，可以总结成一个模板。

遇到这种“最少凑出目标值”的问题，你不要急着硬凑答案，先想想三个问题：能不能把目标拆成更小的子目标？子目标之间有没有重叠？从子目标到当前目标需要的“动作”是什么？如果都能答清，那 DP 的思路基本就定了。后面遇到别的变体，比如“输出四位完全平方数”“判断是否能拆成两个平方数之和”，你也会习惯性地从枚举平方数开始下手。

2. 动态规划的完整推导：从递归到一维数组

2.1 先用记忆化搜索验证思路

在直接写 DP 之前，我建议你先跑一版记忆化搜索，因为它最接近人类自然思维。下面这个 Python 代码直接用lru_cache缓存递归结果，逻辑上和上面的 f(n) 完全一样。

from functools import lru_cache def num_squares_recursive(n: int) -> int: @lru_cache(None) def dfs(x: int) -> int: if x == 0: return 0 ans = x # 最坏情况全用 1，一共 x 个 j = 1 while j * j <= x: ans = min(ans, dfs(x - j * j) + 1) j += 1 return ans return dfs(n)

这里ans初始化为 x，是因为无论如何，用 x 个 1 一定能凑出 x，所以答案不可能超过 x。while循环遍历所有小于等于 x 的平方数。你可能会问，为什么递归往下走到x - j*j，而不走到“加了一个平方数”之前的状态？因为我们是反着看的：从结果往回推，最后一步加上某个平方数，那么之前的状态就是去掉这个平方数之后的值。

我实测这版代码在小 n 上很快，但到了 n=10000，因为 Python 递归深度和缓存开销，会比后面要讲的迭代 DP 慢一截。不过它最大的价值是逻辑清晰，适合上课和验证正确性。

2.2 状态定义与状态转移方程

从递归式可以直接得到迭代版：用一个数组 dp，让 dp[i] 表示凑出整数 i 需要的最少完全平方数个数。那么初始情况是 dp[0] = 0，因为凑出 0 不需要任何数。其他位置一开始可以设成一个很大的数，比如float('inf')，代表“还没算出来”。

状态转移方程如下：

dp[i] = min(dp[i - j*j] + 1) 对所有满足 j*j <= i 的 j 取最小值

这个方程的含义是：i 的最后一步可以加 1²、2²、3²……只要不超过 i。加上最后一步之后，剩余部分 i - j² 已经在上一步算好了。我们取所有方案里最小的一档，就是 dp[i]。

这个推导过程跟“爬楼梯”很像，只不过爬楼梯能用的步数是 1 或 2，这里是所有平方数。区别在于这里步数集合也是可变的，但都可以通过枚举 j 来处理。你可以把 dp 当成一个“按数字从小到大记录最优答案的账本”，后面的每一项都从前面已经算好的项取最合理的一笔加一。

2.3 手推一遍：n=12 的 dp 数组

光看公式容易飘，我建议你亲手推几个值。下面这张表是我把 n=12 的整个 dp 数组列出来的结果。

推到 i=12 的时候，内层枚举 j=1、2、3，因为 4²=16 已经超过 12。三个候选值分别是 dp[11]+1=4、dp[8]+1=3、dp[3]+1=4，取最小得到 3。这个过程特别能说明动态规划的“最优子结构”：dp[12] 的最优解依赖于 dp[8] 的最优解，而 dp[8] 又是靠 dp[4] 推出来的，环环相扣，没有一处需要回头重新算整个子问题。

这个表也提醒我们，dp 数组的更新顺序必须是 i 从小到大。如果从大到小，计算 dp[12] 时 dp[8] 还没算出来，结果就废了。这也是自底向上 DP 最容易犯的毛病之一。

2.4 为什么这里只需要一维数组

有人可能会想：题目里既要用平方数，又要选个数，怎么不是二维 DP？这是很多初学者的困惑。其实是否需要二维，取决于状态里有几个独立的维度。这里我们最后只要求“最少个数”，而完全平方数可以重复使用，所以不需要记录“当前用到了第几个平方数”。你只要把“可选面额集合”固定成所有平方数，问题就退化成了每个目标 i 上的一个最小值问题。

换句话说，一维 DP 已经把“所有平方数都能用”这个信息隐含在 dp[i] 的定义里了。对比一下 0-1 背包问题，那里每个物品只能用一次，所以状态必须额外记录“考虑了前几个物品”，才是二维 DP。完全平方数没有这个限制，因此用一维数组就够了。这个判断对以后做题很有用：先想清楚状态要记录哪些信息，再决定数组的维度。

3. 用 Python 实现动态规划：代码、优化与另一条路

3.1 最标准的迭代动态规划代码

有了前面的推导，写出标准 DP 就很简单了。下面是 Python 的参考实现。

import math def num_squares(n: int) -> int: # dp[i] 表示凑出 i 需要的最少完全平方数个数 dp = [float('inf')] * (n + 1) dp[0] = 0 for i in range(1, n + 1): r = math.isqrt(i) for j in range(1, r + 1): dp[i] = min(dp[i], dp[i - j * j] + 1) return dp[n]

这里我特意用了math.isqrt而不是int(math.sqrt(i))。isqrt是 Python 3.8 开始提供的整数开方函数，返回的是整数部分。浮点数sqrt在数据量大的时候虽然也很稳，但毕竟经过了浮点表示，偶尔会带来精度问题。更重要的是isqrt本身就是整数运算，和理解完全平方数的语义完全匹配。

运行这段代码，输入 n=12 会返回 3，输入 n=13 会返回 2。逻辑闭环，代码很短，这也是为什么这道题非常适合当 DP 入门题的原因。

3.2 两个实用的代码小优化

标准的写法没问题，但有几个小改动能让代码更顺手。第一种是把 dp 初值从float('inf')换成list(range(n+1))，因为最坏情况全用 1 凑，dp[i] = i 一定成立，所以可以直接用 i 作为初值。

def num_squares_v2(n: int) -> int: dp = list(range(n + 1)) squares = [j * j for j in range(1, int(n ** 0.5) + 1)] 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]

第二种是预先把所有小于等于 n 的平方数都生成成一个列表squares，这样内层不需要反复算j*j，而且在平方数列表里遇到大于 i 的元素可以直接 break。因为squares是递增的，所以 break 不会漏掉后面的元素，只会跳过所有无效的大平方数。

这两个优化对 n 不大的题目提升不明显，但你能养成两个好习惯：一是不在循环里重复造轮子，二是初值必须符合逻辑。很多时候刷题到最后拼的不是会不会写，而是能不能一眼看出哪些写法是安全且可维护的。

3.3 换个角度：用 BFS 求最短层数

动态规划是从小到大填表，BFS 的思路则是从 n 开始一层一层往外扩散。每一层代表“用了 k 个平方数”，能到达哪些数。比如第 1 层从 n 减去所有平方数，得到一批更小的数；第 2 层再对这批数继续减平方数。第一次遇到 0 的时候，使用的层数就是答案。

from collections import deque def num_squares_bfs(n: int) -> int: squares = [i * i for i in range(1, int(n ** 0.5) + 1)] queue = deque([n]) seen = {n} level = 0 while queue: level += 1 for _ in range(len(queue)): curr = queue.popleft() for s in squares: if s > curr: break nxt = curr - s if nxt == 0: return level if nxt not in seen: seen.add(nxt) queue.append(nxt) return -1

这段代码里最关键的一行是if nxt not in seen。如果没有去重，一个数字可能通过不同路径反复进入队列，复杂度和内存都会爆炸。我之前第一次写 BFS 时偷懒没加 seen，结果 n=10000 直接跑了几分钟都没出来，后来才意识到问题出在哪。加入 seen 之后，每个数字最多被访问一次，实际速度经常比 DP 还快，因为 BFS 一旦找到答案就提前结束，不会机械地算完所有 i。

这个思路本质上和图论里的无权最短路径是一回事：每个整数是一个节点，每减去一个平方数就是一条边，边的权重都是 1，找的是 n 到 0 的最短路径。如果你熟悉 BFS，用这道题来练习“把最优化问题建模成图”会很有收获。

3.4 数学优化：四平方和定理与三平方定理

聊完 DP 和 BFS，还得提一提升级版的数学方法。Lagrange 四平方和定理说，任何正整数都能表示成不超过 4 个整数的平方和。而 Legendre 三平方定理告诉我们，一个数不能表示成 3 个平方数之和，当且仅当它形如 4^a × (8b+7)。换句话说，只要 n 不是这种特殊形状，答案最大就是 3；如果恰好是这种形状，答案就是 4。在这个基础上，再排除完全平方数（答案 1）和能表示成两个平方数之和（答案 2）的情况，就能直接出结果。

import math def num_squares_math(n: int) -> int: def is_square(x: int) -> bool: r = math.isqrt(x) return r * r == x if is_square(n): return 1 temp = n while temp % 4 == 0: temp //= 4 if temp % 8 == 7: return 4 for i in range(1, math.isqrt(n) + 1): if is_square(n - i * i): return 2 return 3

这个解法看着很短，实际坑特别多。我踩过最痛的坑是判断顺序：一开始我在判断完完全平方数之后，直接去枚举两个平方数，发现某些答案应该是 4 的数被返回了 2。后来才意识到，必须先处理4^a(8b+7)这个特殊形状，否则会把“需要 4 个”的数误判成“可以拆成两个平方数”。因为在特殊情况里，原数虽然也能被拆成四个，但枚举两个平方数时刚好碰上了某一种看似合法的拆法，逻辑就错了。

另外，枚举两个平方数的循环最好用math.isqrt(n)做上限，不要写int(n**0.5)然后一上来就用浮点数算，后者在边缘数据上并不总让人放心。

3.5 三种解法怎么选：复杂度与场景对比

我把三种思路放在一起比较，方便你按场景选择。

我个人在面试中最推荐先写 DP：它不需要背定理，代码也不长，面试官容易验证你的思路。BFS 可以作为“如果题目要求返回方案”时的参考答案，因为 BFS 天然能记录路径。数学公式虽然快，但要解释清楚定理就有点负担，除非时间充裕，否则不建议上来就写。

3.6 Python 语言特性对实现的影响

最后补充一点和 Python 本身相关的东西。CPython 的循环效率相对一般，所以遇到 O(n√n) 这种规模的时候，能减少内层计算量就尽量少。用math.isqrt是整数运算，通常比math.sqrt再转换要快一点点；把平方数列表预先算好，也能省去每一轮循环里的乘法。

如果你在本地用 PyPy 跑，这种纯循环的 DP 代码通常会有很大提升，PyPy 对循环的即时编译优化做得比 CPython 好。刷题网站上如果只提供 CPython 环境，也不用太担心，n 一万的规模不算大，正常写法都能通过。真正要小心的是别在循环里写一些花哨的推导式或频繁调用外部函数，比如min([dp[i - s] + 1 for s in squares if s <= i])，虽然看着简洁，但会多创建临时列表，内存和速度都不如直接写for循环加min更新。

4. 常见问题与排查技巧实录

4.1 用错初值导致答案永远是 0

很多人第一次写这段代码，会用dp = [0] * (n+1)，然后在循环里求min(dp[i], dp[i - s] + 1)。问题在于 dp[i] 初值是 0，所以 min 的结果永远是 0，答案全部变成 0。这种错误在本地测试时特别容易被掩盖，因为一旦 n 很小，0 并不会明显违反直觉。排查这种问题最快的方法是打印前几个 dp 值，看看是不是全部都是 0。

正确的初值选择有两种，要么float('inf')，要么i。我个人更推荐用float('inf')，因为它在语义上就是“未被更新过”，跟后面的min配合得很自然。如果你用i做初值，也要记得确实给 dp[0]=0，否则计算 dp[1] 时会出问题。

4.2 内层循环 j 从 0 开始或漏了等号

另一个高频错误是j = 0开始。0²=0，dp[i] = min(dp[i], dp[i-0]+1)，这等于min(dp[i], dp[i]+1)，永远不可能更新出更小值。不仅如此，如果代码里没做额外保护，还可能导致无限循环或多余遍历。正确写法是从 1 开始。

还有就是把while j * j <= i写成while j * j < i。这会导致完全平方数 i 本身不被使用，比如 n=4，正确结果是 1，错误写法会算成 2（4=1+1+1+1）。这种错误只影响特定边界，很难一眼看出来，所以最好的办法是写完带上题目示例跑一遍。

4.3 预生成平方数列表时 break 的位置

用平方数列表squares时，要注意列表必须递增，才能用if s > i: break来提前结束。如果你不小心把一个乱序的平方数列表拿来用，break 就会漏掉后面更大的平方数。我惯用的生成方式是[j*j for j in range(1, int(n**0.5)+1)]，它天然是递增的，但有些人图省事直接手写一个不完整列表，问题就会藏在里面。

另外，int(n**0.5)在 n=9999 这类数上不会出问题，但n**0.5毕竟是浮点运算，如果追求严谨，我还是建议用math.isqrt(n)。

4.4 用变体题巩固：输出所有四位完全平方数

如果你觉得自己只是“看懂了代码”，还没有“会写”，我建议用几个变体题来练手。比如“输出四位范围内的所有完全平方数”，这道题不需要 DP，但它能帮你熟悉完全平方数的生成方式：从 32 到 99 的平方就是所有四位完全平方数，因为 32²=1024，99²=9801。写一遍循环，你会发现对“平方数间隔越来越大”的直觉更深刻。

再比如“判断一个数是否能拆成两个完全平方数之和”，这其实就是数学解法里的那一段枚举逻辑。你可以反向利用 DP 的 dp[i] 值：如果 dp[i]=2，说明它能拆成两个完全平方数。这些变体题共同点都是在训练同一套“枚举平方数 + 状态更新”的肌肉记忆。

4.5 常见问题速查表

我把刷题时高频出现的问题整理成一张表，方便你定位。

这张表并不复杂，但每个问题我都亲眼见过，也在本地调试过。刷题写代码，最怕的不是思路难，而是不知不觉被一个边界条件拖住。把常见问题提前记住，至少能省下很多排错时间。

4.6 调试实录：从 dp 数组定位问题

我再分享一个真实的调试过程。有一次我写了个 DP 版本，n=12 的结果变成了 4，而不是 3。我没急着猜，而是打印了前 12 个 dp 值。结果发现 dp[8]=4，而正确值应该是 2。当时我愣了一下，因为 8 用 4+4 明明只要 2 个平方数。

我对着代码口算了一遍 dp[8] 的更新过程：j=1 时得到 dp[7]+1=5，j=2 时得到 dp[4]+1=2，按理说结果应该是 2。可打印出来却是 4，说明 dp[4] 本身算错了。继续往上看，dp[4] 应该等于 1，但打印结果是 3。问题就出在初值上，我把dp = [i for i in range(n+1)]写成了dp = [n] * (n+1)，导致 dp[4] 的初始值变成了 12，明面上不该出现的超大数污染了所有后续计算。

这个经历说明，动态规划出错时不要只盯着转移方程，先检查初值和循环范围。把 dp 数组完整打印出来，对照手算几个关键下标，通常一眼就能定位。

结尾

这道完全平方数做下来，我最深的体会是：动态规划并没有那么可怕，关键是把“状态”和“转移”这两个词想透。它和贪心的区别在于不贪图局部最优，而是老老实实把所有可能试一遍，再用子问题的最优解拼出大问题的最优解。你只要把 dp[i] 的含义写在纸上，把转移方程的候选来源画出来，剩下的就是代码层面的熟练度了。

最后再分享一个我个人的小习惯：刷完这道题，我会顺手用同一套 DP 模板去写零钱兑换、爬楼梯、单词拆分这些问题。你会发现它们的状态定义和转移方程都长得很像，只是“候选来源”不同。把这个模板变成肌肉记忆，以后再遇到这类最优化问题，至少不会慌。