Leetcode-279题:Perfect Squares

题目：

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)