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 += 1 13 14 dp = [MAX]*(n+1) 15 dp[0] = 1 16 for x in perfect: 17 dp[x] = 1 18 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 4 12 13 a = 0 14 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 2 19 if a == 0 and b>0: 20 return 1 21 if a>0 and b==0: 22 return 1 23 a += 1 24 return 3

?

轉載于:https://www.cnblogs.com/lettuan/p/6183123.html

總結

以上是生活随笔為你收集整理的Leetcode 279. Perfect Square的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。