Perfect Squares - Java Solution

1. Introduction

In this blog post, we explore the "Perfect Squares" problem, a classic challenge in dynamic programming and number theory. The problem asks to find the minimum number of perfect square numbers that sum up to a given integer. A perfect square is an integer that is the square of another integer (e.g., 1, 4, 9, 16). This problem is often encountered in mathematical computations and algorithmic puzzles.

Problem

Given an integer n, the objective is to return the least number of perfect square numbers whose sum equals n. The task involves identifying a set of perfect square numbers that add up to n with the smallest possible count.

2. Solution Steps

1. Use dynamic programming to solve the problem.

2. Create an array dp with n + 1 elements, where dp[i] represents the minimum number of perfect squares that sum to i.

3. Initialize dp[0] to 0, as the sum of 0 requires 0 numbers.

4. Iterate from 1 to n, and for each i, calculate dp[i]:

a. Initialize dp[i] to a maximum value.

b. Iterate through all perfect squares less than or equal to i.

c. Update dp[i] as the minimum of its current value and dp[i - square] + 1.

5. Return dp[n], which represents the least number of perfect squares summing to n.

3. Code Program

public class PerfectSquares {
    public static void main(String[] args) {
        int n = 12;
        System.out.println(numSquares(n)); // Test the function
    }

    // Function to find the least number of perfect squares summing to n
    public static int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
}

Output:

3

Explanation:

1. numSquares: This function computes the least number of perfect squares that sum to n.

2. It initializes a dynamic programming array dp, with dp[i] indicating the minimum number of perfect squares needed to sum to i.

3. The array is filled with a maximum value initially, except for dp[0], which is 0.

4. For each i from 1 to n, the function iterates through all possible perfect squares j * j that are less than or equal to i. It updates dp[i] to the minimum of its current value and 1 + dp[i - j * j].

5. The function returns dp[n], which gives the minimum count of perfect squares required to sum to n.

6. This approach effectively finds the optimal solution by considering all combinations of perfect squares that sum to each number up to n.