## Description

https://leetcode.com/problems/perfect-squares/

Given an integer `n`

, return *the least number of perfect square numbers that sum to* `n`

.

A **perfect square** is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1`

, `4`

, `9`

, and `16`

are perfect squares while `3`

and `11`

are not.

**Example 1:**

Input:n = 12Output:3Explanation:12 = 4 + 4 + 4.

**Example 2:**

Input:n = 13Output:2Explanation:13 = 4 + 9.

**Constraints:**

`1 <= n <= 10`

^{4}

## Explanation

Dynamic programming dp[i] means what is the minimum number of square numbers to add up to equal to i.

## Python Solution

```
class Solution:
def numSquares(self, n: int) -> int:
square_nums = [i**2 for i in range(0, int(sqrt(n)) + 1)]
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
for square in square_nums:
if i < square:
break
dp[i] = min(dp[i], dp[i - square] + 1)
return dp[n]
```

- Time Complexity: O(N).
- Space Complexity: O(N).

where Q is the length of queries and N is the length of colors.

I found this solution very popular and helpful: https://www.youtube.com/watch?v=QzU9oKjT1bo&ab_channel=EricProgramming