題目：

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.

思路：首先構(gòu)造出小于n的平方序列，然后將n拆分為兩部分，一個是某個平方數(shù)的整數(shù)倍，另一個是余數(shù)，在所有拆分的可能中選擇需要次數(shù)最小的即可。計算余數(shù)所需最少次數(shù)與問題具有相同結(jié)構(gòu)，因而可遞歸求解，并且在求解過程中會涉及計算重復問題，所以需保留中間解的答案。

代碼：

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)