@@ -0,0 +1,1479 @@
+%22%22%22%0AGiven a positive integer n, find the least number of perfect square numbers (for%0Aexample, 1, 4, 9, 16, ...) which sum to n.%0A%0AFor example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return%0A2 because 13 = 4 + 9.%0A%0ACredits:%0A    Special thanks to @jianchao.li.fighter for adding this problem and creating%0A    all test cases.%0A%22%22%22%0Aclass Solution(object):%0A    def numSquares(self, n):%0A        %22%22%22%0A        :type n: int%0A        :rtype: int%0A        %22%22%22%0A        dp = collections.defaultdict(int)%0A        j = 1%0A        while j ** 2 %3C= n:%0A            dp%5Bj ** 2%5D = 1%0A            j += 1%0A        for i in range(1, n + 1):%0A            j = 1%0A            while i + j ** 2 %3C= n:%0A                if i + j ** 2 not in dp or dp%5Bi%5D + 1 %3C dp%5Bi + j ** 2%5D:%0A                    dp%5Bi + j ** 2%5D = dp%5Bi%5D + 1%0A                j += 1%0A        return dp%5Bn%5D%0A%0Aimport collections%0Aa = Solution()%0Aprint(a.numSquares(12) == 3)%0Aprint(a.numSquares(13) == 2)%0Aprint(a.numSquares(9925) == 2)%0A%0A%22%22%22%0AFast (O%5Csqrt(n)) solution based on Lagrange's Four-Square Theorem:%0AOriginal C++ code is here:%0Ahttps://discuss.leetcode.com/topic/49126/simple-math-solution-4ms-in-c-explained-now%0A    def numSquares(self, n):%0A        while n %25 4 == 0:%0A            n /= 4%0A        if n %25 8 == 7:%0A            return 4%0A        i = 0%0A        while i ** 2 %3C= n:%0A            j = int(math.sqrt(n - i ** 2))%0A            if i ** 2 + j ** 2 == n:%0A                return int(i != 0) + int(j != 0)%0A            i += 1%0A        return 3%0A%22%22%22%0A%0A

add 279