Problem Statement

Given a positive integer n, determine the smallest number of perfect squares that sum to n. A perfect square is an integer equal to the square of another integer — for example, 1, 4, 9, and 16 are perfect squares; 3 and 11 are not.

Naive Recursiev Approach

A top-down recursive solution defines minSquares(x) as the minimum count of perfect squares required to sum to x. The base case is minSquares(0) = 0. For any x > 0, iterate over all integers k such that k² ≤ x, and recursively compute 1 + minSquares(x − k²), taking the global minimum.

public int numSquares(int n) {
    return computeMin(n);
}

private int computeMin(int remaining) {
    if (remaining == 0) return 0;
    int result = Integer.MAX_VALUE;
    for (int root = 1; root * root <= remaining; root++) {
        result = Math.min(result, 1 + computeMin(remaining - root * root));
    }
    return result;
}

This approach suffers from exponential time complexity due to repeated subproblem evaluations.

Optimized Bottom-Up Dynamic Programming

Since only one parameter (remaining) varies and its domain is [0, n], we use a 1D DP array dp of size n + 1. Initialize dp[0] = 0, and for each i from 1 to n, compute:

dp[i] = min{ dp[i − j²] + 1 } for all j where j² ≤ i

The recurrence reflects choosing a perfect square j², then solving the residual sum i − j² optimally.

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int value = 1; value <= n; value++) {
        for (int side = 1; side * side <= value; side++) {
            int remainder = value - side * side;
            if (dp[remainder] != Integer.MAX_VALUE) {
                dp[value] = Math.min(dp[value], dp[remainder] + 1);
            }
        }
    }
    return dp[n];
}