0279._perfect_squares.md

279. Perfect Squares

题目: https://leetcode.com/problems/perfect-squares/

难度:

Medium

思路一：

DP, 状态转移方程:

dp[i] = min(dp[i], dp[i - j * j] + 1)

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

但是这个方法贼慢，beats 12%, 有时候提交甚至会超时，有时候又不会。。。。因此想别的办法

思路二：

Static DP, beats 90.39%

class Solution(object):
    dp = [0]
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        while len(self.dp) <= n:
            m = len(self.dp)
            inf = float('inf')
            i = 1
            while i * i <= m:
                inf = min(inf, self.dp[m-i*i] + 1)
                i += 1
            self.dp.append(inf)
        return self.dp[n]

进一步简化可以写成：

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

这里有个问题现在还没搞明白，以后再好好想一下，写成return self.dp[-1]提交就失败，

Submission Result: Wrong Answer
Input: 1024
Output: 4
Expected: 1

思路三：

还是慢，有个数学方法, runtime beats 98.48%

import math
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        def isSquare(num):
            tmp = int(math.sqrt(num))
            return tmp * tmp == num
        while n & 3 == 0: # n % 4 == 0 
            n >>= 2
        if n & 7 == 7: # n % 8 == 7
            return 4
        if isSquare(n):
            return 1
        sqrt_n = int(math.sqrt(n))
        for i in range(1, sqrt_n + 1):
            if isSquare(n-i*i):
                return 2
        return 3

in order to understand, I suggest u read:

here is the Lagrange's Four Square theorem - Limit the result to <= 4:

And this article, in which you can also find the way to present a number as a sum of four squares: