题干：
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n =12输出: 3 解释:12 = 4 + 4 + 4.
示例 2:
输入: n =13输出: 2 解释:13 = 4 + 9.
解题报告：
很多人第一眼看到这个问题，想到的第一种做法就是使用贪心算法，但是对于这个问题是不适用的，例如：
如果贪心来做，12 = 9 + 1 + 1 + 1，所以答案为4了，但是实际答案是3。
我们根据题目中完全平方数的个数最少，看到最少，想到最短路，建图跑最短路就行了。一种不错的思考方式但是此题会TLE。
下面介绍一个数学定理：
四平方和定理：
Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。（万能的拉格朗日Orz）
即：结果只有1,2,3,4，四种可能。
还有一个重要的推论：
也就是说我们可以先判断这个数是否满足
处理方法是：
while (myN & 3 == 0) {
myN >>= 2;
}
if (myN % 8 == 7) {
return 4;
} 然后我们再暴力破解ans=1和ans=2的情况，如果都不满足，那就直接ans=3。
class Solution:
_dp = list()
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
dp = self._dp
dp = [float('inf') for i in range(n + 1)]
dp[0] = 0
for i in range(n + 1):
j = 1
while i + j**2 <= n:
dp[i + j**2] = min(dp[i + j**2], dp[i] + 1)
j += 1
return dp[n]
参考博客https://blog.csdn.net/qq_17550379/article/details/80875782
京公网安备 11010502036488号