本文共 1397 字，大约阅读时间需要 4 分钟。

1. 问题描述：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12

示例 2:

输入: n = 13

2. 思路分析：

① 分析题目可以知道我们可以尝试去拼凑数字n由若干个平方数的组成方案，尝试搜索所有的可能性，一个比较容易想到的思路是使用dfs搜索，对于当前的数字n最大的平方数字为当前的平方根取整之后的数字，比如数字10最大的平方数是9所以我们可以从index为3往前开始搜索拼凑，从后面比较大的数字往前面搜索的一个好处是我们可以设置一个全局变量，对于python来说可以设置成一个类变量，用来更新当前能够组成n的最小数目，我们知道从后面往前面搜索的话使用的是比较少的数字，所以第一次找到的方案有可能使用的数字的数量是最少的，比如10可以由9 + 1组成，求解出一个方案之后那么我们更新类变量这样在往下递归的时候就可以使用这个条件来进行剪枝缩短递归的时间，接下来只有当前求解的方案的数目小于之前的res彩往下进行求解了，这样比从前往后求解会缩小很多的时间

② 从题目中可以看到当前的数字n是可以由多个相同的数字组成的，所以我们是可以利用在循环中递归来尝试相同的数字，这样在往下递归的时候就可以使用相同的数字很多次了

③ 从上面的分析我们可以知道dfs的方法中可以传递四个参数，第一个参数是当前的数字n，第二个参数是到当前为止构成的平方和是多少（递归的出口可以通过这个变量来更新res），第三个参数是平方数的数目，第四个是当前平方根，用来计算出平方数，整个过程还是挺好理解的，注意其中的细节即可，一开始写代码的时候可以借助于pycharm在方法上打上断点进行调试以便更好地观察方法的调用以及各个变量的变换情况

3. 代码如下：

import sysfrom math import sqrtclass Solution:    res = 0    def dfs(self, n: int, cur: int, count: int, index: int):        if cur == n:            if count < Solution.res: Solution.res = count            return            # 从后面往前进行递归: 往前面进行减枝        while index > 0 and count + 1 < Solution.res:            if cur + index * index <= n: self.dfs(n, cur + index * index, count + 1, index)            # 从后面往前进行递归肯定是平方根减小的            index -= 1    def numSquares(self, n: int) -> int:        Solution.res = n        self.dfs(n, 0, 0, int(sqrt(n)))        return Solution.res