问题描述
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
问题分析
Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
如果知道这个定理，就可以首先将答案限定在[1, 4]区间中，证明见链接。
但还需确定具体的解。有如下两条规则：
- 如果n可以被4整除，那么n/4和n是可以用相同个完全平方数表示的。
- 如果n可表示为4a(8b+7)，那么n可表示为4个完全平方数之和。
但是我没有找到上面两条规则的证明……
在运用完上面两条规则后，再判断是1还是2，剩下的是3。
AC代码
数论方法：Runtime: 39 ms
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
a = 0
while a * a <= n:
b = int((n - a * a) ** 0.5)
if a * a + b * b == n:
return 1 if a == 0 else 2
a += 1
return 3
动规方法：Runtime: 189 ms
动规需要注意：将规划数组作为一个类变量，每次增长它才能AC，如果每次重新计算规划数组，则TLE，参考了Discuss内容.
class Solution(object):
d = [0]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
for i in range(len(self.d), n+1):
m = i
j = 1
while j * j <= i:
if j * j == i:
m = 1
break
if self.d[i-j*j] + 1 < m:
m = self.d[i-j*j] + 1
j += 1
self.d.append(m)
return self.d[n]
