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

题目描述

279. 完全平方数

给定正整数 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的列表

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

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

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

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

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

• 在上层中出现, 对应的结果肯定比当前节点更小, 剪枝

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

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

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进行缓存, 减少遍历, 但由于没有简直, 效率依然很低.

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)