# 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))
``````

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