Perfect Squares

Question

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.

Tags

• Dynamic Programming
• BFS
• Math

Thought

Use the dynamic Programing and the recurrence equation is DP[i + j * j] = min(DP[i + j * j], DP[i] + 1).

DP[i] represents the lead number of perfect squares to form the positive integer i.

Code

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        for i in xrange(1, len(dp)):
            dp[i] = sys.maxint
        for i in xrange(n + 1):
            j = 1
            while i + j * j <= n:
                dp[i + j * j] = min(dp[i + j * j], dp[i] + 1)
                j += 1
        return dp[-1]