279. Perfect Squares

Solution 1: DP (Bottom-up)

class Solution:
    def numSquares(self, n: int) -> int:
        minCntOfPerfectSquares = [0] + [10001] * (n)
        for idx in range(1, n+1):
            sqrtVal = 1
            while sqrtVal*sqrtVal <= idx:
                perfectSquare = sqrtVal*sqrtVal
                minCntOfPerfectSquares[idx] = min(minCntOfPerfectSquares[idx], minCntOfPerfectSquares[idx - perfectSquare] + 1)
                sqrtVal += 1
        return minCntOfPerfectSquares[n]

Time Complexity: O(n*sqrt(n))
Space Complexity: O(n)

Solution 1 - 2: DP (Bottom-up) + Static declare

Time Complexity: O(n*sqrt(n))
Space Complexity: O(n)

Solution 2: BFS

class Solution:
    def numSquares(self, n: int) -> int:
        sqrtN = int(n**0.5)
        perfectSquares = [i ** 2 for i in range(1, sqrtN + 1)]
        depth = 1
        bfsQueu = set([n])
        while bfsQueu:
            newQueu = set() # Temporarily store the current level node
            for node in bfsQueu:
                for square in perfectSquares:
                    if square == node:
                        return depth
                    elif square > node:
                        break
                    elif square < node:
                        newQueu.add(node - square)
            bfsQueu = newQueu - bfsQueu # to prune the duplicate calculation, "bfsQueu = newQueu" also works
            depth += 1 # Go to the next level
        return depth

Time Complexity: O(N) // Because we use set to avoid duplicate computing, the total node we are going through is at most O(n)
BFS queue example (n = 15):

15
......
14, 11, 6
......
13, 10, 5, 7, 2
......
12, 9, 4, 6, 1, 3

Space Complexity: O(N)

Solution 3: Math

Time Complexity: O()
Space Complexity: O()

Reference

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)
https://leetcode.com/problems/perfect-squares/discuss/2837770/Python3-DP-with-Detailed-Explanations-O(-n-sqrt(n)-)-not-TLE
https://leetcode.com/problems/perfect-squares/discuss/275311/Python-DP-and-BFS

Follow-up

264. Ugly Number II