LeetCode 279: Perfect Squares

Explanation:

To solve this problem, we can use dynamic programming. We will iterate from 1 to n and for each number i, we will try to find the minimum number of perfect squares that sum up to i. We can do this by considering all possible perfect squares less than or equal to i and finding the minimum among their corresponding sums.

For example, to find the minimum number of perfect squares that sum up to 12:

• For i = 1, we cannot form 12 using only perfect squares, so we skip.
• For i = 2, we cannot form 12 using only perfect squares, so we skip.
• For i = 3, we cannot form 12 using only perfect squares, so we skip.
• For i = 4, we can form 12 by adding 4 three times (4 + 4 + 4), so the answer is 3.
• For i = 5, we consider all possible perfect squares less than 5 which is 4. So, 5 can be formed by adding 1 (5 = 1 + 4) perfect square, so the answer is 2.

We repeat this process for all numbers from 1 to n to find the minimum number of perfect squares required to sum up to n.

public 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];
}