Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
- code
class Solution(object):
def numSquares(self, n):
dp = [0] + [float('inf')]*n
for i in range(1, n+1):
dp[i] = min(dp[i-j*j] for j in range(1, int(i**0.5)+1)) + 1
return dp[n]
- code
class Solution(object):
def numSquares(self, n):
s = {a * a for a in range(1, 101) if a * a <= n}
if n in s:
return 1
for num in s:
if n - num in s:
return 2
for num1 in s:
for num2 in s:
if n - num1 - num2 in s:
return 3
return 4
- code
class Solution(object):
def numSquares(self, n):
s = [i*i for i in range(1,int(math.sqrt(n))+1)] # Square numbers <= n
step = 0 # BFS level
currentLevel = [0] # List of numbers in BFS level step
while currentLevel:
step += 1
nextLevel = set()
for a in currentLevel:
for b in s:
if a+b < n: nextLevel.add(a+b)
if a+b == n: return step # Found n
currentLevel = nextLevel # Remove duplicates
- code
class Solution(object):
def numSquares(self, n):
candidates = collections.deque([0])
visited = set()
potential = [i*i for i in range(1, int(n**0.5) + 1)]
step = 0
while candidates:
step += 1
sz = len(candidates)
for _ in range(sz):
cur = candidates.popleft()
for v in potential:
if v + cur < n and v + cur not in visited:
candidates.append(v + cur)
visited.add(v + cur)
elif v + cur == n:
return step