Get Minimum Squares

JavaView on GFG

Problem Overview

Minimum number of perfect squares summing to n.

Intuition

Minimum number of perfect squares summing to n. BFS or DP.

Algorithm

1DP: dp[i] = min(dp[i - j*j] + 1) for all j where j*j <= i. Base: dp[0]=0.

Common Pitfalls

• Same as LC 279. Precompute squares up to sqrt(n). O(n * sqrt(n)) DP. BFS gives same result.

Get Minimum Squares.java

Java

// Approach: DP. dp[n] = min perfect squares summing to n. dp[i] = min(dp[i - j*j] + 1) for all j*j <= i.
// Time: O(n * sqrt(n)) Space: O(n)
class Solution {
    public int minSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++)
            dp[i] = i;

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

        return dp[n];
    }
}

Was this solution helpful?