教娃编程第710天：用迭代加深 DFS 求完全平方数的最少数量

本文解析 LeetCode 279「完全平方数」的一种迭代加深递归解法。借助拉格朗日四平方和定理，算法只需依次判断一个数能否由一个、两个或三个完全平方数组成；如果都不能，答案必然是四。文章还分析了该递归实现的复杂度及优化方法，并与动态规划、广度优先搜索和纯数论解法进行比较。

视频：油管/Youtube | B站/小破站 | 微博视频 | 公众号视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook | Instagram

LeetCode 279：完全平方数

这是一题非常经典的面试题，而且有多种解法。

给定一个正整数 n，题目要求找出和为 n 的完全平方数的最少数量。

例如：

• 12 = 4 + 4 + 4，所以答案是 3。
• 13 = 4 + 9，所以答案是 2。
• 16 本身就是完全平方数，所以答案是 1。

这道题的常规解法包括动态规划和广度优先搜索。不过，我们还可以利用限深搜索和拉格朗日四平方和定理，写出一个非常简洁的递归解法。

由数学定理引导的递归搜索

代码如下：

from math import isqrt

class Solution:
    def numSquares(self, n: int) -> int:
        sqrs = [i * i for i in range(1, isqrt(n) + 1)]

        def f(cur, i):
            if i == 1:
                return cur in sqrs

            for x in sqrs:
                if f(cur - x, i - 1):
                    return True

            return False

        for i in range(1, 4):
            if f(n, i):
                return i

        return 4

这段代码虽然很短，但其中包含了几个非常重要的思想。

生成所有完全平方数

第一行代码生成所有不大于 n 的正完全平方数：

sqrs = [i * i for i in range(1, isqrt(n) + 1)]

例如，当 n = 13 时：

sqrs = [1, 4, 9]

我们需要考虑的最大平方数是：

isqrt(n) * isqrt(n)

Python 的 isqrt() 会直接返回准确的整数平方根，不需要使用浮点数运算。通常情况下，它比下面这种写法更合适：

int(n ** 0.5)

当 n 较小时，两种写法都可以正常工作。但是，isqrt() 的含义更加明确，并且可以避免大整数可能遇到的浮点数精度问题。

f(cur, i) 表示什么？

递归函数 f(cur, i) 回答的是一个“是或否”的问题：

cur 能否恰好表示为 i 个正完全平方数之和？

例如：

• f(13, 1) 判断 13 本身是不是一个完全平方数。
• f(13, 2) 判断 13 能否表示为两个完全平方数之和。
• f(12, 3) 判断 12 能否表示为三个完全平方数之和。

当只剩下一个平方数需要选择时，问题就变成了一次简单的成员查找：

if i == 1:
    return cur in sqrs

如果 cur 是一个完全平方数，就说明找到了满足条件的表示方法。

否则，函数会选择一个平方数，将它从当前数值中减去，然后递归判断剩余部分能否由更少的平方数组成：

for x in sqrs:
    if f(cur - x, i - 1):
        return True

每一层递归都会重新从 sqrs 的开头遍历，因此同一个平方数可以被重复选择。这一点非常重要，因为有些答案需要重复使用相同的平方数，例如：

12 = 4 + 4 + 4

为什么只需要检查一个、两个和三个平方数？

外层循环按照平方数数量从少到多依次检查：

for i in range(1, 4):
    if f(n, i):
        return i

需要注意的是，range(1, 4) 只会生成：

1, 2, 3

算法并没有真正搜索由四个平方数组成的情况。如果前三次搜索全部失败，就直接返回 4。

这样做的依据是拉格朗日四平方和定理：

每一个正整数都可以表示为至多四个整数平方数之和。

因此，这道题的答案只可能是 1、2、3 或者 4。

算法按照从小到大的顺序检查这些答案，所以第一次成功时，得到的一定是最少数量。如果使用一个、两个或者三个完全平方数都无法组成 n，那么答案就只能是 4。

这个数学定理不仅仅是一个小优化。它正是递归搜索深度可以被限制在常数范围内的根本原因。

示例：n = 13

算法首先计算：

f(13, 1)

因为 13 不在 [1, 4, 9] 中，所以结果为 False。

接下来计算：

f(13, 2)

假设循环选择了 4，递归调用就会变成：

f(13 - 4, 1)
f(9, 1)

因为 9 是一个完全平方数，所以函数返回 True。也就是说：

13 = 4 + 9

最终答案是 2。

示例：n = 12

只使用一个平方数的搜索会失败，因为 12 不是完全平方数。

只使用两个平方数的搜索也会失败，因为 12 无法表示为两个正完全平方数之和。

在搜索三个平方数时，递归可以找到：

12 - 4 = 8
8 - 4 = 4

剩余的 4 是完全平方数。因此：

12 = 4 + 4 + 4

答案是 3。

一个性能细节：sqrs 是列表

下面的表达式会进行线性查找，因为 sqrs 是一个列表：

cur in sqrs

令 m = floor(sqrt(n))，那么列表中一共有 m 个完全平方数。

在搜索三个平方数时，递归可能需要先选择两个平方数，然后才执行最后的成员查找。在最坏情况下，操作次数大约为：

m * m * m

因此，原始代码最坏情况下的时间复杂度是：

O(m³) = O(n^(3/2))

递归深度最多只有三层，所以递归栈使用的空间是常数级别。存储所有平方数的列表需要 O(sqrt(n)) 空间。

对于这道题相对较小的数据范围，这个简洁的实现仍然可以通过。不过，如果使用集合进行成员查找，就可以将平均查找时间降低到常数级别。

改进后的递归版本

我们可以保留原来的核心思路，同时增加一个集合用于快速查找，并在当前平方数已经过大时提前结束循环：

from math import isqrt

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i * i for i in range(1, isqrt(n) + 1)]
        square_set = set(squares)

        def can_sum(cur, count):
            if count == 1:
                return cur in square_set

            # 剩余的 count - 1 个平方数都至少为 1
            limit = cur - (count - 1)

            for square in squares:
                if square > limit:
                    break

                if can_sum(cur - square, count - 1):
                    return True

            return False

        for count in range(1, 4):
            if can_sum(n, count):
                return count

        return 4

递归仍然执行限深搜索，但最后一步判断一个数是否为完全平方数时，现在平均只需要 O(1) 时间。

对于三个平方数的情况，算法最多枚举两层平方数，第三个平方数通过集合直接判断。其最坏时间复杂度大约可以降低为：

O(m²) = O(n)

剪枝条件还可以阻止递归继续探索那些已经不可能容纳足够数量正完全平方数的分支。

动态规划

这道题最常见的通用解法是动态规划。

定义 dp[x] 表示组成 x 所需要的最少完全平方数数量。如果最后选择的平方数是 s，那么状态转移方程为：

dp[x] = min(dp[x], dp[x - s] + 1)

完整实现如下：

from math import isqrt

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i * i for i in range(1, isqrt(n) + 1)]
        dp = [0] + [float("inf")] * n

        for value in range(1, n + 1):
            for square in squares:
                if square > value:
                    break

                dp[value] = min(
                    dp[value],
                    dp[value - square] + 1
                )

        return dp[n]

当 n = 12 时，部分状态如下：

• dp[1] = 1，使用一个 1。
• dp[4] = 1，使用一个 4。
• dp[8] = 2，使用 4 + 4。
• dp[12] = 3，使用 4 + 4 + 4。

算法一共有 n 个状态，每个状态最多需要检查 sqrt(n) 个完全平方数。

复杂度为：

• 时间复杂度：O(n sqrt(n))
• 空间复杂度：O(n)

动态规划的正确性并不依赖拉格朗日四平方和定理，而且很容易扩展到其他最少硬币数、最少元素组合等类似问题。

广度优先搜索

我们还可以把这道题理解为一个无权图中的最短路径问题。

将每一个“剩余数值”看成图中的一个节点。从数值 x 出发，可以减去任何一个不大于 x 的完全平方数，从而到达下一个节点。

例如，从 13 出发，可以到达：

13 - 1 = 12
13 - 4 = 9
13 - 9 = 4

每一条边代表选择了一个完全平方数。因此，从 n 到 0 的最短距离，就是所需要的最少平方数数量。

from collections import deque
from math import isqrt

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i * i for i in range(1, isqrt(n) + 1)]

        queue = deque([(n, 0)])
        seen = {n}

        while queue:
            remaining, depth = queue.popleft()

            for square in squares:
                if square > remaining:
                    break

                next_remaining = remaining - square

                if next_remaining == 0:
                    return depth + 1

                if next_remaining not in seen:
                    seen.add(next_remaining)
                    queue.append((next_remaining, depth + 1))

BFS 会先检查所有只使用一个平方数的表示方法，然后检查使用两个平方数的情况，再检查三个平方数的情况，以此类推。因此，它第一次到达 0 时，所经过的层数就是最少平方数数量。

最坏情况下的复杂度为：

• 时间复杂度：O(n sqrt(n))
• 空间复杂度：O(n)

从本质上看，BFS 和动态规划解决的是同一个状态转移问题。动态规划按照数值顺序填充状态，而 BFS 按照距离起点的层数逐层探索状态。

纯数学解法

我们还可以进一步利用数论，几乎完全避免动态规划、BFS 和递归枚举。

这个解法结合了两个数学定理：

• 拉格朗日四平方和定理保证答案最多为四。
• 勒让德三平方和定理可以判断一个整数什么时候无法表示为三个平方数之和。

勒让德三平方和定理指出，一个正整数无法表示为三个整数平方数之和，当且仅当它可以写成下面的形式：

4^a * (8b + 7)

因此，可以得到下面的实现：

from math import isqrt

class Solution:
    def numSquares(self, n: int) -> int:
        def is_square(value):
            root = isqrt(value)
            return root * root == value

        if is_square(n):
            return 1

        for a in range(1, isqrt(n) + 1):
            if is_square(n - a * a):
                return 2

        reduced = n

        while reduced % 4 == 0:
            reduced //= 4

        if reduced % 8 == 7:
            return 4

        return 3

整体逻辑如下：

1. 如果 n 本身是完全平方数，返回 1。
2. 如果存在某个 a，使得 n - a² 也是完全平方数，返回 2。
3. 不断移除因子 4 后，如果剩余数字模 8 等于 7，则返回 4。
4. 否则，在已经排除答案 1 和 2 的情况下，答案一定是 3。

这种方法的时间复杂度为 O(sqrt(n))，额外空间复杂度为 O(1)。从渐进复杂度来看，这是最快的解法，但它依赖特定的数学定理，无法像动态规划那样直接推广到普通的硬币组合问题。

不同解法对比

解法	时间复杂度	空间复杂度	主要优点
原始限深 DFS	O(n^(3/2))	O(sqrt(n))	代码非常简洁，直接利用四平方数上界
使用集合查找的 DFS	O(n)	O(sqrt(n))	保留优雅的递归结构，同时提高查找效率
动态规划	O(n sqrt(n))	O(n)	通用性强，容易扩展到类似问题
广度优先搜索	O(n sqrt(n))	O(n)	具有直观的最短路径解释
数论	O(sqrt(n))	O(1)	理论复杂度最优

总结

这个递归解法最有意思的地方，在于它将暴力搜索与一个强有力的数学上界结合起来。如果没有拉格朗日四平方和定理，在只检查前三种情况后直接返回 4 是缺乏逻辑依据的。有了这个定理，递归搜索的深度就永远不需要超过三层。

因此，与其将这个算法简单地称为暴力递归，不如称为“由数学定理引导的迭代加深限深搜索”。

原始实现已经非常简洁、易懂。它最主要的性能问题是 cur in sqrs 会对列表进行线性查找。增加一个集合后，就可以将完全平方数判断的平均时间复杂度降低到 O(1)，从而显著降低整个搜索的最坏时间复杂度。

对于这道特定题目，数论解法的效率最高。不过，从学习可复用算法模式的角度来看，动态规划和 BFS 更有价值。限深递归解法则处于两者之间：代码简洁、思路直观，同时很好地展示了数学知识如何大幅缩小算法的搜索空间。

教娃编程

• 教娃编程第710天：用迭代加深 DFS 求完全平方数的最少数量
• 时代不同, 我儿子10岁就能通过github pages做一个静态网站了
• 教娃编程 vLog: Harness Engineering - 指挥 AI 干活
• AI Coding Agent 正在重塑编程的门槛: 没有AI根本不会写代码了, AI让我严重降智[裂开]
• 教娃(比教媳妇)编程/数学更有成就感
• 娃开始每天都在刷力扣, 他长大以后想当软件工程师
• 当了UP主四年多: 油管/Youtube上传了700多期视频, 2000个粉丝
• 写在教娃编程700天, what's next?
• 写在教娃编程视频300天

• 教娃编程第710天：用迭代加深 DFS 求完全平方数的最少数量
  本文解析 LeetCode 279「完全…
• 教娃编程 vLog: Harness Engineering – 指挥 AI 干活
  这篇文章记录了一次教孩子用 VS Cod…
• 教娃(比教媳妇)编程/数学更有成就感
  从2020年11月22日开始第一课，那时…
• 教娃编程有趣的瞬间 vlog视频集合
  教娃700天：写在教娃编程700天, w…
• 写在教娃编程700天, what’s next?
  今年明显减少了教孩子编程的频率。从年初的…

英文：Teaching Kids Programming – Minimum Number of Perfect Squares via Theorem-guided iterative deepening DFS

本文一共 2718 个汉字, 你数一下对不对.