Given a integer n, detremine the minimum number of perfect squares that sum to n. A perfect square is a integer that equals another integer multiplied by itself.

For example:

• 1, 4, 9, and 16 are perfect squares.
• 3 and 11 are not.

Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4

Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9

The approach uses dynamic programming:

1. Define dp[i] as the minimal count of perfect squares summing to i.
2. Initialize dp[i] = i for all i from 1 to n, since worst case uses i ones.
3. For each value i from 1 to n, iterate through all valid perfect squares j*j where j*j <= i. Update dp[i] using the recurrence relation: dp[i] = min(dp[i], dp[i - j*j] + 1).

Here's the implementation:

public class Solution {
    public int numSquares(int target) {
        int[] memo = new int[target + 1];
        
        // Initialize array with default values
        for (int idx = 1; idx <= target; idx++) {
            memo[idx] = idx;
        }
        
        // Fill the DP table
        for (int current = 1; current <= target; current++) {
            for (int square = 1; square * square <= current; square++) {
                int diff = current - square * square;
                memo[current] = Math.min(memo[current], memo[diff] + 1);
            }
        }
        
        return memo[target];
    }
}

Time complexity: O(n * √n) Space complexity: O(n)