此为本人在学习Python过程中遇到的案例做的学习笔记，案例来自《Python算法指南——程序员经典算法分析与实现》，源代码参考该书及网上资料，若表达有误请指正，谢谢！

给定一个正整数n，找到若干个完全平方数（例如：1，4，9，…），使得它们的和等于n，并且使完全平方数的个数最少。

给出n = 12，返回3，因为12 = 4 + 4 + 4； 给出n = 13，返回2，因为13 = 4 + 9； 给出n = 15，返回4，因为15 = 1 +1 + 4 + 9.

一开始，我的想法是用递归的方法，每次减去一个小于等于n的最大完全平方数，并将得到的差赋给n，用一个函数进行递归，每次调用记录数+1，直到得到的差为0。

例如13 - 9 = ,4，记录数为1；4 - 4 = 0，记录数为2；函数最后一级返回2. 但是问题在于12 = 4 + 4 +4，如果用这种思路得到的将是12 = 9 + 1 + 1 + 1，即返回4. 因此这个方法不可行。

于是尝试使用列举的方法进行寻找规律，在列了几十个数后发现，完全平方数由本身组成，返回1；部分数如10,13等由两个完全平方数组成，返回2；诸如7,15,23等数由四个完全平方数组成，返回3；其余数均由三个完全平方数组成。

这样一来问题就比较好解决了，由于sqrt（）开方返回的是一个浮点数，若（int（sqrt（n）））** 2等于n本身，那么就说明n是一个完全平方数，返回1；取i在1至int（sqrt（n））中的整数，若i ** 2 + （int（sqrt（n - i）））** 2 = n，那么说明n由两个完全平方数组成，返回2；返回4的一系列数中可找出规律为n = 7 + 8k，即n对8取余得到7；余下的数便是返回3了。

书中给出的源代码也是如此操作的，源代码如下：

再将l中的余数送入队列q中，进行下一轮探索； 将余数作为索引，此轮被减数x作为值，更新访问标志矩阵

直到队列中元素都被探索完了或者有某个余数变为0，循环终止，代表最短路径搜索完毕

第一次循环： x = 14 q = deque([]) l = [13 10 5] l = [13 10 5]#第一次更新 l = [13 10 5]#第二次更新 q = deque([13 10 5]) a = [-1 -1 -1 -1 -1 14 -1 -1 -1 -1 14 -1 -1 14 14] #索引为5，10，13的访问标志被更新为14，表示该处值由14作为被减数减去sq得到 循环条件成立，循环继续

第二次循环： x = 13 q = deque([10, 5]) l = [12 9 4] l = [12 9 4]#第一次更新 l = [12 9 4]#第二次更新 q = deque([10, 5, 12, 9, 4]) a = [-1 -1 -1 -1 13 14 -1 -1 -1 13 14 -1 13 14 14] #索引为的4，9，12的访问标志被更新为13，表示该处值由13作为被减数减去sq得到 循环条件成立，循环继续

第三次循环： x = 10 q = deque([5, 12, 9, 4]) l = [9 6 1] l = [9 6 1]#第一次更新 l = [6 1]#第二次更新，索引为9处已有值，去掉元素9 q = deque([5, 12, 9, 4, 6, 1]) a = [-1 10 -1 -1 13 14 10 -1 -1 13 14 -1 13 14 14] #索引为的1，6的访问标志被更新为10，表示该处值由10作为被减数减去sq得到 循环条件成立，循环继续

第四次循环： x = 5 q = deque([12, 9, 4, 6, 1]) l = [ 4 1 -4] l = [ 4 1]#第一次更新，去掉-4 l = []#第二次更新，1，4都已存入q中待探索 q = deque([12, 9, 4, 6, 1]) a = [-1 10 -1 -1 13 14 10 -1 -1 13 14 -1 13 14 14] #状态不变 循环条件成立，循环继续

第五次循环： x = 12 q = deque([9, 4, 6, 1]) l = [11 8 3] l = [11 8 3]#第一次更新 l = [11 8 3]#第二次更新 q = deque([9, 4, 6, 1, 11, 8, 3]) a = [-1 10 -1 12 13 14 10 -1 12 13 14 12 13 14 14] #索引为3，8，11的访问标志被更新为12，表示该处值由12作为被减数减去sq得到 循环条件成立，循环继续

第六次循环： x = 9 q = deque([4, 6, 1, 11, 8, 3]) l = [8 5 0] l = [8 5 0]#第一次更新 l = [0]#第二次更新，5已探索过，8已存入q中待探索 q = deque([4, 6, 1, 11, 8, 3, 0]) a = [ 9 10 -1 12 13 14 10 -1 12 13 14 12 13 14 14] #索引为0的访问标志被更新为9，表示该处值由9作为被减数减去sq得到 循环条件不成立，循环结束

5.接下来便是按照探索路径反着回去取出该最短路径 余数为0时a矩阵的值为最后一段，该值作为最后一段的被减数，减去它本身得到零，为最后一段路径的完全平方数，输出该路径； 同时，该值又是上一路径的索引，可以取出上一路径的被减数，与其相减即可得到上一路径的一个完全平方数，输出该路径； 以此类推，取到第一段路径的数为n，路径全都被取出。