Perfect Squares - Python Solution

1. Introduction

The "Perfect Squares" problem is a classic instance of dynamic programming that involves number theory and combinatorics. It asks to find the least number of perfect square numbers that sum up to a given integer n. A perfect square is an integer that is the square of another integer. This problem is key for understanding the application of dynamic programming in optimizing number partitions.

Problem

Given an integer n, the task is to return the least number of perfect square numbers whose sum equals n. A perfect square is an integer that is the product of some integer with itself, such as 1, 4, 9, and 16.

2. Solution Steps

1. Use dynamic programming to build up a solution from smaller subproblems.

2. Initialize an array dp with length n + 1, where dp[i] represents the least number of perfect squares that sum to i.

3. Set each element in dp to a maximum value initially.

4. Set the base case dp[0] = 0 as there are 0 squares needed to sum to 0.

5. Iterate through each number up to n and for each, check all possible square numbers that could contribute to its sum.

6. Update dp[i] with the minimum count of squares required for each sum.

7. Return the value of dp[n] as the answer.

3. Code Program

def numSquares(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]

# Example Usage
print(numSquares(12))
print(numSquares(13))

Output:

3
2

Explanation:

1. Dynamic Programming Array: dp array is used to store the minimum number of squares required to sum up to each value up to n.

2. Iterative Computation: The function iteratively computes the minimum number of squares for each value from 1 to n.

3. Square Numbers Exploration: For each value, it explores all square numbers less than or equal to that value to find the minimum combination.

4. Updating dp: The dp array is updated with the least count of squares needed for each sum.

5. Result Calculation: The value of dp[n] provides the least number of perfect squares that sum up to n.

6. Optimized Solution: This approach efficiently finds the solution using dynamic programming, avoiding redundant computations.