Perfect Squares.md

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

import numpy as np
class Solution(object):
    #DFS can't work because time, You should use BFS instead
    def numSquares(self, n):
		# Edge case, if it's 1 just return 1, or if it's negative, just return itself
		# because all the n^2 are positive numbers
		if n < 2:
			return n


		# Construct a list of candidate that are perfect square numbers
		# and less than our target number
		lst = []
		i = 1
		while i * i <= n:
			lst.append( i * i )
			i += 1


		cnt = 0
		# Initialize BFS queue
		toCheck = collections.deque()
		toCheck.append(n)

		while toCheck:
			# Increment count each level down
			cnt += 1   
			size = len(toCheck)
			# Iterate through all nodes in current level
			for _ in range(size):
				cur_target = toCheck.popleft()
				# Each candidate in the list is a BFS direction. 
				# We move to that direction by substracting it.
				for candidate in lst:
					# return case
					if cur_target == candidate:
						return cnt
					# This is because our original candidate list is built based on n
					# As we continue to BFS to lower level, the target number gets smaller
					# so we need to make sure we don't go out of range
					if cur_target < candidate:
						break
					toCheck.append(cur_target-candidate)

		return cnt
    def numSquares1(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=0:
            return 0
        max_possible=int(np.sqrt(n))
        self.record=[-2]*n
        global_min=self.explore(n,max_possible+1)
        
        return global_min
    def explore(self,n,max_possible):
        if n<=2 and n>=0:
            return n
        if n<0:
            return -1
        if self.record[n-1]!=-2:
            return self.record[n-1]
        local_min=n
        for k in range(max_possible,1,-1):
            remain=n-k**2
            #print(remain)
            if remain>0:
                count=self.explore(remain,int(np.sqrt(remain))+1)
                self.record[remain-1]=count
                if count!=-1:
                    local_min=min(local_min,count+1)
            if remain==0:
                self.record[remain-1]=1
                local_min=min(local_min,1)
                break
        if local_min==n:
            return -1
        return local_min

Solution: https://leetcode.com/problems/perfect-squares/