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.

 

这道题首先想到的算法是DP。每个perfect square number对应的解都是1。先生成一个n+1长的DP list。对于每个i，可以用dp[i] = min(dp[j] + dp[i-j], dp[i])来更新，这里j 是<= i 的一个perfect square number。但是DP的算法超时。

1 class Solution(object): 2     def numSquares(self, n): 3         """ 4         :type n: int 5         :rtype: int 6         """ 7         MAX = 2147483647 8         m = 1 9         perfect = [m]10         while m**2 <= n:11             perfect.append(m**2)12             m += 113         14         dp = [MAX]*(n+1)15         dp[0] = 116         for x in perfect:17             dp[x] = 118         19         for i in range(2, n+1):20             curP = [x for x in perfect if x <= i]21             for j in curP:22                 dp[i] = min(dp[j] + dp[i-j], dp[i])23         24         return dp[-1]

 

解法二： 来自 https://www.cnblogs.com/grandyang/p/4800552.html

任何一个正整数都可以写成最多4个数的平方和。然后又两条性质可以简化题目：

1. 4q 和 q 的答案一样，i.e. 3, 12。

2. 如果一个数除以8余7 <=> 答案是4。

1 class Solution(object): 2     def numSquares(self, n): 3         """ 4         :type n: int 5         :rtype: int 6         """ 7         while n % 4 == 0: 8             n = n//4 9         10         if n % 8 == 7:11             return 412         13         a = 014         while a**2 <= n:15             b = int(math.sqrt(n - a**2))16             if a**2 + b**2 == n:17                 if a>0 and b>0:18                     return 219                 if a == 0 and b>0:20                     return 121                 if a>0 and b==0:22                     return 123             a += 124         return 3