# \[279]\[中等]\[动态规划]\[背包]\[BFS] 完全平方数

## 题目描述

[279. 完全平方数](https://leetcode-cn.com/problems/perfect-squares/)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

```
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
```

示例 2:

```
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
```

## 解题思路

### 动态规划

以背包的角度来思考, `n`为背包的大小, 每个完全平方数是一个物品, 每个完全平方数可以使用多次, 因此是一个**完全背包**问题. 依据完全背包问题的套路, 应定义状态`dp[i, t]`为对于正整数`t`, 拆解为前`i`个完全平方数之和, 对应的最少数量.

考虑这个问题, 对于一个固定的数`t`, 它能最少拆分成几个完全平方数之和是确定的, 因此只需要定义状态`dp[t]`, 代表正整数`t`, 最少可以拆分成几个完全平方数之和. 再使用完全背包问题的状态转移公式即可.

另外:

* 对于正整数`n`, 可能拆解成的最大完全平方数是`square(ceil(sqrt(n)))`, 只需要先将这些数算出来即可
* 每个正整数`n`, 最多可以拆分为`n`个`1`组成, 因此初始化的时候可以将状态向量定义为1到n的列表

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

        dp = list(range(n + 1))
        for i in range(1, n + 1):
            for sqr in squares:
                if sqr > i:
                    break
                dp[i] = min(dp[i], dp[i - sqr] + 1)
        return dp[-1]
```

### BFS

[动态规划+BFS 逐行解释 python3](https://leetcode-cn.com/problems/perfect-squares/solution/dong-tai-gui-hua-bfs-zhu-xing-jie-shi-python3-by-2/)

使用动态规划的方法, 我们将`1`到`n`的所有数字对应的结果都遍历了一遍. 但大多数情况下, 我们无需遍历`n`之前的每一个数字, 只需要按需搜索.

首先, 继承来自动态规划中的一个思想, 即对于数字`t`, 它最少可以拆分成几个完全平方数之和, 是固定的. 而**按需**搜索, 指的是, 对于数字`n`, 我们每次从中拆出一个完全平方数, 然后将剩余的数字继续递归地, 每次拆解一个完全平方数, 直到剩余的数字为0.

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F9ef163f622c2bb1e48e018397e62c38fa854640d.png?generation=1601089831762808\&alt=media)

上面的这种思路因此可以用DFS或BFS的思路解决. 但本题中不能使用DFS, 只能使用BFS. 这是因为, 我们每次拆出一个完全平方数, 因此可以**隐式地**将遍历的节点**分层**, 每一层代表固定的拆分的完全平方数的数量. 在BFS的情况下, 遍历完一层才会去找下一层, 这样在遍历过程中, 我们缓存搜索见过的节点, 而当遍历到的当前节点在之前出现过时, 只可能有两种情况:

* 在同一层中出现. 由于同一个数字可以拆解的最少完全平方是相同, 即后面的层数相同, 因此同层前面的这个数字的结果可以代表, 当前结点无需继续向下拆解, 剪枝
* 在上层中出现, 对应的结果肯定比当前节点更小, 剪枝

这就是按照BFS遍历的优势, 便于剪枝.

需要特别注意下面代码中遍历过程中控制层数的方法.

```python
class Solution:
    def numSquares(self, n: int) -> int:
        squares = [i ** 2 for i in range(1, int(math.sqrt(n)) + 1)]
        if n == 0:
            return 0

        queue, seen = [n], set([n])
        steps = 0
        while queue:
            steps += 1  # 遍历到下一层, 数量加1
            num_current_layer = len(queue)  # 当前层中结点的数量
            for _ in range(num_current_layer):  # 遍历当期层中的所有结点
                number = queue.pop(0)
                for sqr in squares:
                    if sqr > number:
                        break

                    left = number - sqr
                    if left == 0:
                        return steps
                    if left not in seen:
                        seen.add(left)
                        queue.append(left)
        return steps
```

### DFS

使用DFS的思路实现一遍, 结合LRU进行缓存, 减少遍历, 但由于没有简直, 效率依然很低.

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

        @lru_cache(None)
        def dfs(number):
            if number == 0:
                return 0

            min_steps = 1e12
            for sqr in squares:
                if sqr > number:
                    break

                min_steps = min(min_steps, dfs(number - sqr) + 1)
            return min_steps
        return dfs(n)
```