問(wèn)題描述
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.
問(wèn)題分析
Lagrange 四平方定理： 任何一個(gè)正整數(shù)都可以表示成不超過(guò)四個(gè)整數(shù)的平方之和摔认。
如果知道這個(gè)定理炼杖，就可以首先將答案限定在[1, 4]區(qū)間中让网，證明見(jiàn)鏈接。
但還需確定具體的解蛮拔。有如下兩條規(guī)則：
- 如果n可以被4整除，那么n/4和n是可以用相同個(gè)完全平方數(shù)表示的。
- 如果n可表示為4a(8b+7)碉怔，那么n可表示為4個(gè)完全平方數(shù)之和逾滥。
但是我沒(méi)有找到上面兩條規(guī)則的證明……
在運(yùn)用完上面兩條規(guī)則后峰档，再判斷是1還是2，剩下的是3寨昙。
AC代碼
數(shù)論方法：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
動(dòng)規(guī)方法：Runtime: 189 ms
動(dòng)規(guī)需要注意：將規(guī)劃數(shù)組作為一個(gè)類(lèi)變量讥巡，每次增長(zhǎng)它才能AC，如果每次重新計(jì)算規(guī)劃數(shù)組舔哪，則TLE欢顷，參考了Discuss內(nèi)容.
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]
