Perfect Squares

Problem: Perfect Squares

The solution actually evolves from the brute-force solution. We use a trick to improve the performance. First is to use a global dynamic programming array to store calculated results so that we won't do duplicate calculation.

Code in Python:

class Solution(object):
    dp = [0]

    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if len(self.dp) <= n:
            perfectSqr = [v**2 for v in xrange(1, int(math.sqrt(n)) + 1)]
            for i in xrange(len(self.dp), n + 1):
                self.dp.append( min(1 + self.dp[i - sqr] for sqr in perfectSqr if sqr <= i))
        return self.dp[n]