Perfect Square

题目描述

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.

解题方法

数论

数论的方法，任意一个数都可以用不多于4个平方和表示出来

DP

  • 建立一个长度为n+1的array dp
  • 对于是平方和的数，dp[i] = 1
  • 对于i从1到n，只要i + k ^ 2 <= n, 就尝试更新dp[i+k^2]的值

Solution

数论

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

        while n % 4 == 0:
            n /= 4

        if n % 8 == 7:
            return 4

        a = 0
        while (a ** 2) <= n:
            b = int(math.sqrt(n - a ** 2))
            if ((a**2) + (b**2)) == n:
                if a == 0:
                    return 1
                else:
                    return 2
            a += 1

        return 3

python DP, 过不了时间

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

        dp = [sys.maxint for i in range(n+1)]
        root = 1
        while (root ** 2) <= n:
            dp[root**2] = 1
            root += 1

        for i in range(1, n+1):
            root = 1
            while i + (root ** 2) <= n:
                dp[i+(root**2)] = min(dp[i+(root**2)], dp[i] + 1)
                root += 1

        return dp[n]

Reference