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

1. 问题描述：

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

示例 1:

输入: n = 12

示例 2:

输入: n = 13

2. 思路分析：

一开始我想到的是所有可能的组合的方法去解决的，看了一下领扣的题解之后发现可以使用bfs来解决，对于bfs思路解决都是类似的解题套路，需要借助于队列来解决，对于python语言来说可以使用列表就可以模拟整个队列，主要的步骤如下：

(1) 初始化队列（列表）的第一个节点，可以将第一个节点的值设置为n

(2) 在队列（列表）不为空的情况下弹出对首的第一个节点，然后加入当前弹出节点的邻接点，我们可以对当前节点1-k的平方根进行拼凑，比如弹出队列的第一个节点n = 12, 尝试减去1,2...k的平方，k的值为n的平方根，也就是3，所以第一次加入的邻接节点是12 - 1 = 11. 12 - 2 * 2 = 8, 12 - 3 * 3 = 3,即11,8,3这三个邻接点，在循环中都是进行相同的操作：弹出对首节点，加入邻接点

(3) 由(2)可知最后肯定有一个平方数的组合的节点的值为0的，最小到达0的这个节点肯定使用的数目是最小的，所以直接返回即可（画出一颗二叉树会更好理解先到达的肯定是最小的）

(4) 还需要注意的是需要对访问过的节点进行标记，这样可以避免重复访问的问题

3. 代码如下：

在领扣中发现一个写的比较好的代码，使用到了一个python在循环中初始化列表的一个技巧：

大佬的代码如下：

class node:    def __init__(self, value, step=0):        self.value = value        self.step = stepclass Solution:    def numSquares(self, n: int) -> int:        queue = [node(n)]        visited = set([node(n).value])        while queue:            vertex = queue.pop(0)            residuals = [vertex.value - n * n for n in range(1, int(vertex.value ** .5) + 1)]            for i in residuals:                new_vertex = node(i, vertex.step + 1)                if i == 0:                    return new_vertex.step                elif i not in visited:                    queue.append(new_vertex)                    visited.add(i)        return -1

转载地址：http://hagr.baihongyu.com/