279.md

279 Perfect Squares

Description

link

---

Solution BFS

• See Code traditional BFS. find the minimum conditions(use states)

---

Code

Complexity T : O(sqrt(n))) M : O(sqrt(n))

class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = [1]
        i = 2
        while i * i <= n:
            nums.append(i * i)
            i += 1
        
        q = set([n])
        cnt = 1
        while True:
            tmp = set()
            for x in q:
                for y in nums:
                    if x < y:
                        break
                    if x == y:
                        return cnt
                    else:
                        tmp.add(x - y)
            cnt += 1
            q = tmp