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

# 279 Perfect Squares

## 279. [Perfect Squares](https://leetcode.com/problems/perfect-squares/description/)

## 1. Question

Given a positive integern, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`) which sum ton.

For example, givenn=`12`, return`3`because`12 = 4 + 4 + 4`; givenn=`13`, return`2`because`13 = 4 + 9`.

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public int numSquares(int n) {
        int upperBound = (int)Math.sqrt(n);
        int[] squares = new int[upperBound];

        for (int i = 1; i <= upperBound; i++) {
            squares[i - 1] = i * i;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);

        boolean[] visited = new boolean[n + 1];
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            ++level;

            for (int i = 0; i < size; i++) {
                int curNum = queue.remove();
                visited[curNum] = true;

                for (int square : squares) {
                    int nextNum = curNum + square;

                    if (nextNum > n) {
                        break;
                    }
                    else if (nextNum == n) {
                        return level;
                    }
                    else if (!visited[nextNum]) {
                        queue.add(nextNum);
                    }
                }
            }
        }
        return level;
    }
}
```

**(2) DP**

```java
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= (int)Math.sqrt(i); j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}
```

**(3) Memoization**

```java
public class Solution {
    public int numSquares(int n) {
        int[] cache = new int[n + 1];
        return dfs(n, cache);
    }

    public int dfs(int n, int[] cache) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (cache[n] != 0) {
            return cache[n];
        }

        int num = Integer.MAX_VALUE;

        for (int i = 1; i * i <= n; i++) {
            num = Math.min(num, dfs(n - i * i, cache) + 1);
        }
        cache[n] = num;
        return num;
    }
}
```

## 3. Time & Space Complexity

**BFS:** 时间复杂度O(n \* sqrt(n)), 空间复杂度O(n)

**DP:** 时间复杂度O(n \* sqrt(n)), 空间复杂度O(n)

**Memoization:** 时间复杂度O(n \* sqrt(n)), 空间复杂度O(n)