Type: Medium, BFS
完美平方数
题目描述：
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
这里还牵涉到一个理论是：四平方和定理。
所以，本题的答案只在1，2，3，4这四个里面了。
去验证下：
139 / 588 test cases passed.
这个能过139个测试样例的写法是：
import random
class Solution:
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
return random.randint(1,4)
随机1，2，3，4.
再测试只随机输出1，2，3，结果：
160 / 588 test cases passed.
还有提高哈。
严肃说明：这不是解题的正确态度，只是探索一下。
实际上，结合一个推论：
满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足
可以知道，是四个整数组成的，比较特殊。
import random
class Solution:
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# 根据推论，降低问题规模：4^a(8b + 7)
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
a = 0
while a ** 2 <= n:
b = int((n - a ** 2) ** 0.5)
if a ** 2 + b ** 2 == n:
return (not not a) + (not not b)
a += 1
return 3
根据推论，4本身是平方数，所以可以不断除以4，得到的8b + 7假定是，带上4可以看成是
。
缩减到只剩下8b+7后，就可以进行判断是否满足推论，否则开始暴力搜索，满足两个完全平方数的 ，则输出2，否则就是3.
DP解法
import random
class Solution:
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# dp解法
dp = [1e31] * (n + 1)
a = int(n ** 0.5)
for i in range(a + 1):
dp[i * i] = 1
for i in range(1,n + 1):
b = int((n - i) ** 0.5) + 1
for j in range(1,b):
dp[i + j * j] = min(dp[i] + 1, dp[i + j * j])
return dp[n]
参考链接：https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51584790
END.
