Leetcode 279. Perfect Squares

Problem Explanation

The problem is asking for the minimum number of perfect squares that sum to a given number n. A perfect square is a result from an integer being multiplied by itself, such as 1, 4, 9, 16, 25, and so on. The task is to express n as the sum of as few perfect squares as possible.

For example, if the input n is 12, the output should be 3 because 12 can be written as the sum of three perfect squares (4+4+4). If the input n is 13, the output should be 2 because 13 can be written as the sum of two perfect squares (4+9).

Solution Approach

This problem can be solved with dynamic programming. A dynamic programming approach will not just find a solution, but will find an optimal solution by storing and reusing previously calculated results to avoid unnecessary computation. This makes the solution more efficient.

In this approach, an array dp of size n+1 is made to store the least number of perfect squares which sum to every number from 0 to n. For any given number i, we iterate over each perfect square j*j less than or equal to i, and fill dp[i] as minimum of dp[i] and dp[i-j*j] + 1. In the end, dp[n] will hold our result.

To illustrate, let's take n=12 as example:

The initial array will look like this [0,1,2,3,4,5,6,7,8,9,10,11,12].

In the first iteration i=2, for perfect square j*j=1: dp[2] is min(2, dp[2-1]+1)=min(2,2)=2.

In the second iteration i=4, for perfect square j*j=1: dp[4] is min(4, dp[4-1]+1)=min(4,2)=2.

In the third iteration i=4, for perfect square j*j=4: dp[4] is min(2, dp[4-4]+1)=min(2,1)=1.

We keep updating the array till we reach n=12, and finally we have dp[12] = 3.

Code Solutions

Python

1
2python
3class Solution:
4  def numSquares(self, n: int) -> int:
5    dp = [i for i in range(n + 1)]  # i = i*1^2
6    dp[0] = 0  # 0 = 0*1^2
7    for i in range(2, n + 1):
8      j = 1
9      while j * j <= i:
10        dp[i] = min(dp[i], dp[i - j * j] + 1)
11        j += 1
12    return dp[n]

Java

1
2java
3class Solution {
4  public int numSquares(int n) {
5    int[] dp = new int[n + 1];
6    for (int i = 1; i <= n; i++) {
7      dp[i] = i; //maximum is i because 1^2*i = i
8      for (int j = 1; j*j <= i; j++) {
9        dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
10      }
11    }
12    return dp[n];
13  }
14}

JavaScript

1
2javascript
3var numSquares = function(n) {
4    let dp = Array(n + 1).fill(Infinity);
5    dp[0] = 0;
6  
7    for(let i = 1; i <= n; i++) {
8        for(let j = 1; j*j <= i; j++) {
9            dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
10        }
11    }
12  
13    return dp[n];
14};

C++

1
2cpp
3class Solution {
4public:
5    int numSquares(int n) {
6        vector<int> dp(n + 1, INT_MAX);
7        dp[0] = 0; 
8        for(int i=1; i<=n; ++i) {
9            for(int j=1; j*j<=i; ++j) {
10                dp[i] = min(dp[i], dp[i-j*j] + 1);
11            }
12        }
13        return dp[n];
14    }
15};

C#

1
2csharp
3public class Solution {
4    public int NumSquares(int n) {
5        int[] dp = new int[n+1];
6        for(int i=1; i<=n; i++){
7            dp[i] = i;
8            for(int j = 1; j*j<=i; j++){
9                dp[i] = Math.Min(dp[i], dp[i-j*j] + 1);
10            }
11        }   
12        return dp[n];
13    }
14}

Each provided solution in different languages reflects the same approach discussed. The difference lies only in the specific syntax for each language.In terms of time complexity, the solution runs in O(n*sqrt(n)) time whereby 'n' represents the input number and 'sqrt(n)' is for iterating through all squares less than or equal to 'n'. The space complexity is O(n) for storing results in the dp array up to 'n'.

To sum up, this dynamic programming approach effectively calculates the minimum number of perfect square numbers that sum up to a given number. With the reuse of previously calculated information, it avoids unnecessary repeated computation, thus enhancing the efficiency greatly. It is a valuable approach especially when dealing with larger input sizes.