Perfect Squares

Lecture 104:- Perfect Squares

The Perfect Squares problem is a classic dynamic programming problem. Given a positive integer n, you need to find the least number of perfect square numbers (e.g., 1, 4, 9, 16, etc.) that sum up to n.

Here's a Python function that implements the Perfect Squares algorithm using dynamic programming:

pythonCopy code

def num_squares(n):    dp = [float('inf')] * (n + 1)    dp[0] = 0    for i in range(1, n + 1):        j = 1        while j * j <= i:            dp[i] = min(dp[i], dp[i - j * j] + 1)            j += 1    return dp[n] # Test the function print(num_squares(12))  # Output: 3 (12 = 4 + 4 + 4) print(num_squares(13))  # Output: 2 (13 = 4 + 9)

In this code, the num_squares() function takes a positive integer n as input. It creates a dp array to store the minimum number of perfect square numbers needed to sum up to each number from 0 to n.

The dynamic programming approach iterates from 1 to n and tries all possible perfect square numbers to find the minimum number of perfect squares required to reach the current number. The result is stored in dp[n], which represents the minimum number of perfect squares needed to sum up to n.

The time complexity of this solution is O(n * sqrt(n)), where n is the given positive integer. The space complexity is O(n) due to the dynamic programming array dp.