Perfect Squares - Leetcode Solution

The Perfect Squares problem on LeetCode is a popular dynamic programming problem in which we are given a positive integer n and are supposed to find the least number of perfect square numbers that sum up to n. In simpler terms, we need to find out the minimum number of perfect squares whose sum is equal to the given number n.

For example, if the input is 12, the output should be 3 because 12 can be represented as 4 + 4 + 4 or 9 + 1 + 1 + 1. In either case, we need a minimum of 3 perfect squares to represent 12.

To solve this problem, we need to come up with a dynamic programming approach. In this approach, we will maintain a 1D array dp, where dp[i] represents the minimum number of perfect squares required to sum up to i. We can use the following recurrence relation to compute the value of dp[i]:

dp[i] = min(dp[i - j*j] + 1) for j in [1, sqrt(i)]

In simpler terms, we can calculate dp[i] by iterating over all the possible perfect squares jj (where j belongs to [1, sqrt(i)]) and compute dp[i - jj] + 1. We take the minimum of all the computed values and assign it to dp[i].

The base case for this problem is dp[0] = 0 because we need 0 perfect squares to sum up to 0.

Here's a step-by-step solution for the problem:

Step 1: Define the function that takes the input n and returns the minimum number of perfect squares that sum up to n.

Step 2: Create an array dp of size (n+1) and initialize all its values to infinity, except for dp[0] which should be set to 0.

Step 3: Iterate over all the integers i from 1 to n.

Step 4: Iterate over all the possible perfect squares j*j (where j belongs to [1, sqrt(i)]).

Step 5: For each jj, compute dp[i - jj] + 1 and assign the minimum of all such values to dp[i].

Step 6: Return dp[n] as the minimum number of perfect squares that sum up to n.

Here's the Python code implementation of the above solution:

import math

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        
        for i in range(1, n+1):
            for j in range(1, int(math.sqrt(i))+1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[n]

The time complexity of this solution is O(n*sqrt(n)) because we are iterating over n integers and sqrt(n) perfect squares for each integer. The space complexity is O(n) because we are maintaining a 1D array of size (n+1).

Overall, the Perfect Squares problem on LeetCode can be solved using dynamic programming with a time complexity of O(n*sqrt(n)) and space complexity of O(n).

1