题目：
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.
思路：首先构造出小于n的平方序列，然后将n拆分为两部分，一个是某个平方数的整数倍，另一个是余数，在所有拆分的可能中选择需要次数最小的即可。计算余数所需最少次数与问题具有相同结构，因而可递归求解，并且在求解过程中会涉及计算重复问题，所以需保留中间解的答案。
代码：
def getLeast(self, squares, dp, n):
if n == 0:
return 0
elif n in squares:
return 1
elif n in dp:
return dp[n]
else:
t = min([n/k+self.getLeast(squares,dp,n%k) for k in squares if k<=n])
dp[n] = t
return t
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n==None or n<=0:
return -1
squares = []
for i in range(1,n+1):
if i*i > n:
break
squares.append(i*i)
dp = {}
return self.getLeast(squares,dp,n)
