279. Perfect Squares

Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Intuition

To solve this problem, we can use a dynamic programming approach. The idea is to build up a solution for n by using solutions for smaller numbers. Specifically, for each number num from 1 to n, we can find the minimum number of perfect squares that sum to num by considering all perfect squares less than or equal to num.

Approach

1. Memoization Initialization: - Create a memoization array memo of size 10001 and initialize all values to -1. This array will store the minimum number of perfect squares that sum to each index.
2. Recursive Function: - Define a helper function dp(num, memo) that returns the minimum number of perfect squares that sum to num. - Base cases: - If num < 0, return a large number (10000) because it is an invalid case. - If num == 0, return 0 because no squares are needed to sum to zero. - If memo[num] != -1, return the memoized result to avoid redundant calculations. - For each i from 1 to 100, compute the minimum number of squares needed for num - i*i and update mini. - Memoize the result for num.
3. Main Function: - Call the helper function dp(n, memo) to get the result.

Complexity

Time Complexity:

O(n * sqrt(n))

• There are n states and for each state, we loop up to sqrt(n).

Space Complexity:

O(n)

• The memoization array takes up O(n) space.

Code

C++

class Solution {
public:
    int numSquares(int n) {
        vector memo(10001, -1);
        return dp(n, memo);
    }
    
private:
    int dp(int num, vector& memo) {
        if (num < 0) return 10000;
        if (num == 0) return 0;
        if (memo[num] != -1) return memo[num];
        int mini = 100000;
        for (int i = 1; i <= 100; i++) {
            mini = min(mini, 1 + dp(num - i * i, memo));
        }
        return memo[num] = mini;
    }
};

Python

class Solution:
    def numSquares(self, n: int) -> int:
        if n <= 0:
            return 0

        queue = deque([n])
        visited = set([n])

        level = 0
        while queue:
            level += 1
            size = len(queue)
            for _ in range(size):
                current = queue.popleft()
                for i in range(1, int(current**0.5) + 1):
                    remainder = current - i*i
                    if remainder == 0:
                        return level
                    if remainder not in visited:
                        visited.add(remainder)
                        queue.append(remainder)

        return level

Java

class Solution {
    public int numSquares(int n) {
        int[] memo = new int[10001];
        Arrays.fill(memo, -1);
        return dp(n, memo);
    }

    private int dp(int num, int[] memo) {
        if (num < 0) return 10000;
        if (num == 0) return 0;
        if (memo[num] != -1) return memo[num];
        int mini = 100000;
        for (int i = 1; i <= 100; i++) {
            mini = Math.min(mini, 1 + dp(num - i * i, memo));
        }
        memo[num] = mini;
        return mini;
    }
}

JavaScript

var numSquares = function (n) {
    let memo = Array(10001).fill(-1);
    return dp(n, memo);
};
function dp(num, memo) {
    if (num < 0) return 10000;
    if (num === 0) return 0;
    if (memo[num] !== -1) return memo[num];
    let mini = 100000;
    for (let i = 1; i <= 100; i++) {
        mini = Math.min(mini, 1 + dp(num - i * i, memo));
    }
    return memo[num] = mini;
}