Perfect Squares

Finding the least number of perfect square numbers that sum to ( n ) can be solved using a dynamic programming approach. This problem can be thought of as finding the shortest path to reach ( n ) using perfect square numbers as steps.

Approach

  1. Create an Array of Squares: First, we need to identify all the perfect squares that are less than or equal to ( n ).
  2. Dynamic Programming Array: We’ll initialize an array dp of size ( n+1 ) where dp[i] will store the least number of perfect squares that sum to ( i ).
  3. Initialization: dp[0] will be 0 as zero can be represented without any perfect square.
  4. Build Solution: Iterate from 1 to ( n ), and for each value i, iterate through the perfect squares. For each square sq, update dp[i] as the minimum between the current value and dp[i-sq] + 1.
  5. Result: dp[n] will store the final result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numSquares(self, n: int) -> int:
        # Generating list of squares less than or equal to n
        squares = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]

        # Initializing dp array
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        # Building dp array
        for i in range(1, n + 1):
            for sq in squares:
                if i >= sq:
                    dp[i] = min(dp[i], dp[i - sq] + 1)

        return dp[n]

Explanation

  • We iterate through the numbers from 1 to ( n ), and for each number, we consider the possibility of subtracting each square.
  • dp[i - sq] + 1 gives us the number of perfect squares needed for the value i considering the current square sq.
  • We store the minimum value in dp[i], and eventually, dp[n] will hold the result.

Key Takeaways

  • Dynamic programming allows us to build the solution from the ground up.
  • The time complexity of this approach is ( O(n \cdot \sqrt{n}) ).
  • The space complexity is ( O(n) ), which is used to store the dp array.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# @param {Integer} n
# @return {Integer}
def num_squares(n)
  dp = [0] * (n + 1)
  dp[0] = 1
  
  i = 0
  while i <= n
    dp[i] = i
    j = 1

    while j*j <= i
      dp[i] = [dp[i], dp[i - j*j] + 1].min
      j += 1
    end

    i += 1
  end
  
  dp[n]
end