第一种做法是动态规划，用一个数组perfect[i]来记录到perfect[i]数目，perfect[0]=0，对于i来说，任意一个i-jj + jj = i，所以prefect[i] = min(perfect[i], perfect[i-j*j] + 1),把所有perfect[i]初始化为n。代码如下：
import math
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
perfect = [n for i in range(n+1)]
perfect[0] = 0
for i in range(n+1):
for j in range(1,int(math.sqrt(i)+1)):
perfect[i] = min(perfect[i],perfect[i-j*j]+1)
return perfect[-1]
第二种做法是静态动态规划。
import math
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
perfect = []
perfect.append(0)
while len(perfect) <= n:
m = len(perfect)
minc = n
for i in range(1, int(math.sqrt(m))+1):
minc = min(minc,perfect[m-i*i] + 1)
perfect.append(minc)
return perfect[-1]
