Leetcode – 完全平方数

这是我参与更文挑战的第11天，活动详情查看更文挑战

题目描述

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

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

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

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
复制代码

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
复制代码

提示：

• 1 $\le$ n $\le$ 104

解题思路与代码

要把正整数 x 拆分成最少个不同正整数的平方和。

不妨假设有一个现成的函数U = func(x)，其中x表示原正整数，U表示拆解出来的最少个正整数的集合。进一步假设正整数a ∈ U，即a是集合U中的正整数。则必然有：

U - a = func(x - a^2)
复制代码

换句话说，当集合U中元素的个数是 n 的话，则正整数x – a^2 所能拆解出的最少完全平方数之和的集合为U去掉a后的补集。这个结论可以用反证法推出来。

因此，通过上面的分析，我们得到了以下结论

func(x) = 1 + ∑(min(func(x - a^2))), a^2 <= x
复制代码

要对给定的正整数求其最少完全平方数表达，需要枚举位于正整数之前的数的最少完全平方数表达。上面的表达式转换成代码，可以用 DFS，也可以 DP

DFS解法的Python代码

class Solution:
    def num_squares(self, n: int) -> int:
        @lru_cache(None)
        def dfs(k: int) -> int:
            ret = k  # 最差情况是由 k 个 1 组成
            limit = int(k ** 0.5)
            for i in range(limit, 0, -1):
                ret = min(ret, 1 + dfs(k - limit * limit))
            return ret

        return dfs(n)
复制代码