Solution Explanation for Perfect Squares

The problem asks for the minimum number of perfect square numbers that sum up to a given integer n. We can solve this using dynamic programming.

Approach 1: 2D DP

This approach uses a 2D array f where f[i][j] represents the minimum number of perfect squares needed to sum to j using perfect squares up to i*i.

Algorithm:

1. Initialization: Create a 2D array f of size (m+1) x (n+1), where m = √n. Initialize f[0][0] = 0. All other cells are initialized to infinity (or a large number) representing that a solution hasn't been found yet.

2. Iteration: Iterate through the array. For each f[i][j], we consider two possibilities:

   • We don't use i*i: f[i][j] = f[i-1][j]
   • We use i*i: If j >= i*i, then f[i][j] = min(f[i][j], f[i][j - i*i] + 1)

3. Result: f[m][n] will contain the minimum number of perfect squares needed to sum to n.

Time Complexity: O(m*n), where m = √n. Therefore, the overall time complexity is approximately O(n√n).

Space Complexity: O(m*n) which is approximately O(n√n).

Approach 2: 1D DP (Optimized)

This approach optimizes space complexity by using a 1D array.

Algorithm:

1. Initialization: Create a 1D array f of size (n+1). Initialize f[0] = 0 and the rest to infinity (or a large number).

2. Iteration: Iterate through perfect squares up to n. For each perfect square i*i, iterate from i*i to n. For each number j, update f[j] as the minimum of its current value and f[j - i*i] + 1.

3. Result: f[n] will contain the minimum number of perfect squares needed to sum to n.

Time Complexity: O(n√n). The nested loops iterate approximately √n times the number n.

Space Complexity: O(n) because of the 1D array f.

Code Examples (Python)

Approach 1 (2D DP):

import math
from sys import maxsize as inf
 
class Solution:
    def numSquares(self, n: int) -> int:
        m = int(math.sqrt(n))
        f = [[inf] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 0
        for i in range(1, m + 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= i * i:
                    f[i][j] = min(f[i][j], f[i][j - i * i] + 1)
        return f[m][n]
 

Approach 2 (1D DP):

import math
from sys import maxsize as inf
 
class Solution:
    def numSquares(self, n: int) -> int:
        m = int(math.sqrt(n))
        f = [inf] * (n + 1)
        f[0] = 0
        for i in range(1, m + 1):
            for j in range(i * i, n + 1):
                f[j] = min(f[j], f[j - i * i] + 1)
        return f[n]

The provided code examples show implementations in multiple languages, all based on the 1D DP approach for better space efficiency. The 2D DP approach is conceptually easier to understand but less efficient in terms of space. Both approaches have the same time complexity of O(n√n).