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.

Solution: DP

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0

        squares = [float('inf')] * (n + 1)
        squares[0] = 0

        for num in xrange(1, n + 1):
            unit = 1
            sqr = unit * unit
            while sqr <= num:
                squares[num] = min(squares[num], squares[num - sqr] + 1)
                unit += 1
                sqr = unit * unit

        return squares[-1]

Lessons:

• Any number can be split into a square and a smaller number.