# 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.

## Comments

## Post a Comment