> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0279-perfect-squares.md).

# 0279. Perfect Squares

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

## Description

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 = 12
**Output:** 3
**Explanation:** 12 = 4 + 4 + 4.
```

**Example 2:**

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

**Constraints:**

* `1 <= n <= 104`

## ac1: DP

[https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics](https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-%28BFS-DP-static-DP-and-mathematics))

```java
class Solution {
    public int numSquares(int n) {
        // edge cases
        if (n < 4) return n;

        // init
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;;
            for (int k = 1; i - k*k >= 0; k++) {
                min = Math.min(min, dp[i-k*k] + 1);
            }
            dp[i] = min;
        }

        return dp[n];
    }
}

// state: f[i], least number ... 
// function: f[i] = max(f[i-1^2], f[i-2^2]) + 1, while i - k^2 > 0;
```

## ac2: BFS

time limit exceed layer -> need to have `int size = q.size();`

```java
class Solution {
    public int numSquares(int n) {
        // edge cases
        if (n < 4) return n;

        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(n);

        int layer = 0;
        while (!q.isEmpty()) {
            layer++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curr = q.poll();
                for (int k = 1; k*k <= curr; k++) {
                    if (curr - k*k == 0) return layer; 
                    q.offer(curr - k*k);
                }
            }
        }
        return layer;
    }
}
```

[https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)/73744](https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-%28BFS-DP-static-DP-and-mathematics%29/73744)