完全平方数

问题简述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

279. 完全平方数 - 力扣（LeetCode）

思路1：朴素完全背包（超时）

• 定义 dfs(i, j) 表示用 1~i 的完全平方数凑出 j 需要的最小数量；

• 不能 AC，仅离线验证了正确性；

Python：递归

class Solution:
    def numSquares(self, n: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i == 0 and j == 0: return 0  # 显然
            if i == 0: return float('inf')  # 凑不出的情况，返回不可能，注意此时 j != 0
            # if i == 1: return j

            ret = j  # 最大值为 j，因为任意数字最差都可以用 1 组成
            times = 0  # i 使用的次数，0 次也考虑在内
            while (x := (i ** 2) * times) <= j:
                ret = min(ret, dfs(i - 1, j - x) + times)
                times += 1

            return ret

        N = int(n ** 0.5)  # 可以使用数字的范围
        return dfs(N, n)

Python：动态规划（从递归修改而来）

class Solution:
    def numSquares(self, n: int) -> int:
        from functools import lru_cache

        N = int(n ** 0.5)
        dp = [[0] * (n + 1) for _ in range(N + 1)]
        dp[0] = [float('inf')] * (n + 1)
        dp[0][0] = 0

        for i in range(1, N + 1):
            for j in range(1, n + 1):
                dp[i][j] = j
                times = 0
                while (x := i * i * times) <= j:
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - x] + times)
                    times += 1

        return dp[-1][-1]

思路2：完全背包（优化）

• 定义 dfs(j) 表示目标和为j时需要完全平方数的最少个数；

  这里隐含了完全平方数的范围 i*i <= j；

• 【递归基】j == 0 时，返回 0；

Python：递归

class Solution:
    def numSquares(self, n: int) -> int:
        from functools import lru_cache

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

            # 这里设置初始化为一个上界
            #   本题中初始化为无穷大、j（全部 1）、4（四平方和定理）都可以；
            #   为了使解法更通用，故初始化为无穷大
            ret = float('inf')
            i = 1
            while (x := i * i) <= j:
                ret = min(ret, dfs(j - x) + 1)
                i += 1

            return ret

        return dfs(n)

Python：动态规划（从递归修改而来）

class Solution:
    def numSquares(self, n: int) -> int:

        dp = [i for i in range(n + 1)]
        dp[0] = 0

        for j in range(1, n + 1):
            i = 1
            while (x := i * i) <= n:
                dp[j] = min(dp[j], dp[j - x] + 1)
                i += 1

        return dp[-1]

Python：动态规划（更快的写法）

• 交换内外层遍历顺序（本题无影响），减小 j 的遍历范围；

  关于遍历“物品”和“容量”的顺序影响，见：零钱兑换 - 代码随想录

class Solution:
    def numSquares(self, n: int) -> int:

        dp = [i for i in range(n + 1)]
        dp[0] = 0

        i = 1
        while (x := i * i) <= n:
            for j in range(x, n + 1):
                dp[j] = min(dp[j], dp[j - x] + 1)
            i += 1

        return dp[-1]

其他思路

• 数学（时间复杂度 $O(\sqrt{n})$）：完全平方数 - 力扣官方题解

  四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和；

• BFS：完全平方数 - 自来火