The Perfect Squares problem is a classic dynamic programming challenge where the goal is to find the minimum number of perfect square numbers (numbers that can be expressed as the square of an integer) that sum up to a given positive integer ‘n’. In this blog, we’ll explore the problem, understand its intuition, and implement a solution using dynamic programming in Java.

Problem Overview:

Given a positive integer ‘n’, the task is to find the least number of perfect square numbers that sum up to ‘n’.

Example: For n = 12, the minimum number of perfect squares required is 2 (4 + 4 + 4).

Solution Approach:

To solve this problem, we can use dynamic programming to build up a solution by considering smaller subproblems. Let’s create a Java class called Solution and use a recursive approach with memoization to solve the problem.

class Solution {
    int[][] dp;

    public int numSquares(int n) {
        ArrayList<Integer> squaresList = generateSquaresList(n);
        dp = new int[squaresList.size()][n + 1];

        for (int i = 0; i < squaresList.size(); i++) {
            Arrays.fill(dp[i], -1);
        }

        return recurse(squaresList, 0, n);
    }

    int recurse(ArrayList<Integer> squaresList, int currentIndex, int target) {
        if (currentIndex == squaresList.size()) {
            if (target == 0) return 0;
            return Integer.MAX_VALUE - 10;
        }

        if (dp[currentIndex][target] != -1) {
            return dp[currentIndex][target];
        }

        int take = Integer.MAX_VALUE - 10;
        if ((target - squaresList.get(currentIndex)) >= 0) {
            take = 1 + recurse(squaresList, currentIndex, target - squaresList.get(currentIndex));
        }

        int notTaking = recurse(squaresList, currentIndex + 1, target);

        dp[currentIndex][target] = Math.min(take, notTaking);
        return dp[currentIndex][target];
    }

    ArrayList<Integer> generateSquaresList(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            list.add(i * i);
        }
        return list;
    }
}

Explanation:

• We define a function ‘numSquares’ to calculate the minimum number of perfect squares required to sum up to ‘n’.
• The ‘generateSquaresList’ function generates a list of perfect squares up to ‘n’.
• The ‘recurse’ function is a recursive helper function that considers two scenarios: taking the current square or not taking it, and returns the minimum of the two.
• Memoization is applied using a 2D array ‘dp’ to store and reuse previously computed results.

Conclusion:

The Perfect Squares problem demonstrates the power of dynamic programming in solving optimization problems. By breaking down the problem into smaller subproblems and efficiently storing and retrieving intermediate results, we can find an optimal solution. The provided Java code offers a clear implementation of the solution using recursion and memoization.