Perfect squares

这道题就是纯序列堆砌而已，主要在于把时间复杂度优化到O(n^1.5)

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

这道题有个纯数学的O(n^0.5)的解法，任意一个数字一定可以被4个以内的小于它的数字的平方和组合而成，这是一个纯数学定理，证明就呵呵了，反正就是这么一套理论，因为是Snapchat的一道常考题，记下这个答案也是好的

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        while n % 4 == 0:
            n /= 4
        if n % 8 == 7:
            return 4
        for i in xrange(int(n ** 0.5) + 1):
            j = (n - i ** 2) ** 0.5
            if i ** 2 + int(j) ** 2 == n:
                return 2 if i != 0 and j != 0 else 1

        return 3