# LC 279. Perfect Squares

### [Problem link](https://leetcode.com/problems/perfect-squares/)

###### tags: `leedcode` `python` `c++` `medium` `DP` `BFS`

Given an integer <code>n</code>, return the least number of perfect square numbers that sum to <code>n</code>.

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, <code>1</code>, <code>4</code>, <code>9</code>, and <code>16</code> are perfect squares while <code>3</code> and <code>11</code> are not.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

- <code>1 <= n <= 10⁴</code>

## Solution 1 - DP
#### Python

class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i**2 for i in range(1, int(math.sqrt(n)) + 1)]
        dp = [float("inf")] * (n + 1)
        dp[0] = 0

        for square in squares:
            for j in range(square, n + 1):
                dp[j] = min(dp[j], dp[j - square] + 1)

        return dp[-1]

#### C++

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;

        vector<int> nums;
        for (int i = 1; i <= int(sqrt(n)); i++) {
            nums.push_back(i * i);
        }

        for (int i = 0; i < nums.size(); i++) {
            for (int j = nums[i]; j <= n; j++) {
                if (dp[j - nums[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - nums[i]] + 1);
                }
            }
        }
        return dp.back();
    }
};

## Solution 2 - BFS
#### Python

class Solution:
    def numSquares(self, n: int) -> int:
        q = deque([(n, 0)])
        squares = [i**2 for i in range(int(sqrt(n)) + 1)]
        seen = set()

        while q:
            num, res = q.popleft()

            if num == 0:
                return res

            for i in range(1, int(sqrt(num)) + 1):
                candidate = num - squares[i]

                if candidate < 0:
                    continue

                if candidate not in seen:
                    q.append((candidate, res + 1))
                    seen.add(candidate)

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | ----------------- | ---------------- |
>| Solution 1 | O($\sqrt{n}$ * n) | O(n) |
>| Solution 2 | O($\sqrt{n}$ * n) | O($\sqrt{n}$) |

## Note
### sol1:
將平方數當成物品, n=背包容量, 這樣就成了無限背包的題目了.
跟[LC 322. Coin Change](https://hackmd.io/@Alone0506/HJXLBpgS3)一樣

c++:
不確定是否每個數都可以被perfect square組合, 如果會, 則可能會return INT_MAX,
如果不會, 則if (dp[j - nums[i]] != INT_MAX)這個判斷可以拿掉, 因為不會出現dp前面的數字為INT_MAX的情況.

### sol2:
res在每一輪的BFS中都會+1, 所以遇到num == 0直接return res就是最小值了.
sol2 time complexity: 每一輪會跑$\sqrt{num}$次, 最多跑n次, 且num <= n, 所以TC = $\sqrt{n}$ * n, 但sol2的時間複雜度較sol1小.