LeetCode 279. Perfect Squares

Post by ailswan Dec. 26, 2023

279. Perfect Squares

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: n = 12 Output: 3

Input: n = 13 Output: 2

Solution Approach

Dynamic Programming (DP) Solution The dynamic programming solution initializes an array to store the minimum number of perfect squares needed for each value and iterates through all possible square numbers to compute the minimum count for the given integer n. Breadth-First Search (BFS) Solution The breadth-first search solution explores the solution space by subtracting perfect square numbers from the given integer n, incrementing the level of exploration until a perfect square is reached, determining the minimum number of perfect squares required.

Algorithm

Dynamic Programming (DP) Solution:

Initialize an array dp to store the minimum number of perfect squares needed for each value from 0 to n. Iterate through each value, considering all possible square numbers up to the square root of n. Update the minimum count based on the previously computed values, and the final result is the minimum count for n.

Breadth-First Search (BFS) Solution: Start with the given integer n and initialize a level variable to track the exploration depth. Explore all possible reductions by subtracting perfect square numbers from n, incrementing the level with each iteration. Continue the search until a perfect square is reached, and the level of exploration at that point is the minimum number of perfect squares required to sum to n.

Implement

    class Solution:
  def numSquares(self, n: int) -> int:
        square_nums = [i**2 for i in range(1, int(math.sqrt(n)) + 1)]
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                dp[i] = min(dp[i], dp[i - square] + 1)
        return dp[-1]
class Solution2:
  def numSquares(self, n: int) -> int:
      square_nums = [i**2 for i in range(1, int(math.sqrt(n)) + 1)]
      level = 0
      queue = {n}
      while queue:
          level += 1
          tmp = set()
          for num in queue:
              for sq in square_nums:    
                  if num == sq:
                      return level
                  elif num < sq:
                      break
                  else:
                      tmp.add(num - sq)
          queue = tmp