【数据结构与算法】之组成和的完全平方数最少个数的算法

一、题目要求

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

示例一 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4 示例二 输入: n = 13 输出: 2 解释: 13 = 4 + 9

二、示例算法

① 暴力枚举法 [超出时间限制]

这个问题要求我们找出由完全平方数组合成给定数字的最小个数。我们将问题重新表述成： 给定一个完全平方数列表和正整数 n，求出完全平方数组合成 n 的组合，要求组合中的解拥有完全平方数的最小个数。注意：可以重复使用列表中的完全平方数。从上面对这个问题的叙述来看，它似乎是一个组合问题，对于这个问题，一个直观的解决方案是使用暴力枚举法，我们枚举所有可能的组合，并找到完全平方数的个数最小的一个。我们可以用下面的公式来表述这个问题： numSquares(n) = min(numSquares(n-k) + 1)，∀k ∈ square numbers从上面的公式中，我们可以将其转换为递归解决方案。示例算法如下： class Solution(object): def numSquares(self, n): square_nums = [i**2 for i in range(1, int(math.sqrt(n))+1)] def minNumSquares(k): """ recursive solution """ # bottom cases: find a square number if k in square_nums: return 1 min_num = float('inf') # Find the minimal value among all possible solutions for square in square_nums: if k < square: break new_num = minNumSquares(k-square) + 1 min_num = min(min_num, new_num) return min_num return minNumSquares(n) 上面的解决方案可以适用于较小的正整数 n。然而，会发现对于中等大小的数字（例如 55），我们也会很快遇到超出时间限制的问题。简单的说，可能会由于过度递归，产生堆栈溢出。

② 动态规划

使用暴力枚举法会超出时间限制的原因很简单，因为我们重复的计算了中间解。我们以前的公式仍然是有效的，只需要一个更好的方法实现这个公式： numSquares(n) = min(numSquares(n-k) + 1)，∀k∈square numbers你可能注意到从公式看来，这个问题和斐波那契数问题类似。和斐波那契数一样，我们由几种更有效的方法来计算解，而不是简单的递归。解决递归中堆栈溢出的问题的一个思路就是使用动态规划（DP）技术，该技术建立在重用中间解的结果来计算终解的思想之上。要计算 numSquares(n) 的值，首先要计算 n 之前的所有值，即 numSquares(n−k) ∀k∈square numbers。如果我们已经在某个地方保留了数字 n−k 的解，那么就不需要使用递归计算。算法思路如下： 几乎所有的动态规划解决方案，首先会创建一个一维或多维数组 DP 来保存中间子解的值，以及通常数组最后一个值代表最终解。注意，我们创建了一个虚构的元素 dp[0]=0 来简化逻辑，这有助于在在余数 (n-k）恰好是一个完全平方数的情况下。我们还需要预计算小于给定数字 n 的完全平方数列表（即 square_nums）。在主要步骤中，我们从数字 1 循环到 n，计算每个数字 i 的解（即 numSquares(i)）。每次迭代中，我们将 numSquares(i) 的结果保存在 dp[i] 中。在循环结束时，我们返回数组中的最后一个元素作为解决方案的结果。在下图中，我们演示了如何计算与 dp[4] 和 dp[5] 相对应的 numSquares(4) 和 numSquares(5) 的结果。 下面是示例实现，其中 Python 解决方案花费了约 3500 ms，这比当时 50% 的提交要快。需要注意的是：以下 Python 解决方案仅适用于 Python2。出于某种未知的原因，Python3 运行相同的代码需要更长的时间。 class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)] dp = [float('inf')] * (n+1) # bottom case dp[0] = 0 for i in range(1, n+1): for square in square_nums: if i < square: break dp[i] = min(dp[i], dp[i-square] + 1) return dp[-1] 那么 Java 算法如下： class Solution { public int numSquares(int n) { int dp[] = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); // bottom case dp[0] = 0; // pre-calculate the square numbers. int max_square_index = (int) Math.sqrt(n) + 1; int square_nums[] = new int[max_square_index]; for (int i = 1; i < max_square_index; ++i) { square_nums[i] = i * i; } for (int i = 1; i <= n; ++i) { for (int s = 1; s < max_square_index; ++s) { if (i < square_nums[s]) break; dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1); } } return dp[n]; } } 复杂度分析 时间复杂度：O(n⋅$\sqrt{n}$)，在主步骤中有一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 $\sqrt{n}$ 迭代。空间复杂度：O(n)，使用了一个一维数组 dp。

③ 贪心枚举

递归解决方法为我们理解问题提供了简洁直观的方法。我们仍然可以用递归解决这个问题。为了改进上述暴力枚举解决方案，我们可以在递归中加入贪心。我们可以将枚举重新格式化如下： 从一个数字到多个数字的组合开始，一旦找到一个可以组合成给定数字 n 的组合，那么可以说找到了最小的组合，因为贪心的从小到大的枚举组合。

为了更好的解释，首先定义一个名为 is_divided_by(n, count) 的函数，该函数返回一个布尔值，表示数字 n 是否可以被一个数字 count 组合，而不是像前面函数 numSquares(n) 返回组合的确切大小。 numSquares(n) = argmin(is_divided_by(n,count))，count ∈ [1,2,…n]

与递归函数 numSquare(n) 不同，is_divided_by(n, count) 的递归过程可以归结为底部情况（即 count==1）更快。

下面是一个关于函数 is_divided_by(n, count) 的例子，它对 输入 n=5 和 count=2 进行了分解，通过这种重新构造的技巧，我们可以显著降低堆栈溢出的风险。

算法说明

首先准备一个小于给定数字 n 的完全平方数列表（称为 square_nums）。在主循环中，将组合的大小（称为 count）从 1 迭代到 n，检查数字 n 是否可以除以组合的和，即 is_divided_by(n, count)。函数 is_divided_by(n, count) 可以用递归的形式实现，如上面所说。在最下面的例子中，有 count==1，只需检查数字 n 是否本身是一个完全平方数。可以在 square_nums 中检查，即 n ∈square_nums。如果 square_nums 使用的是集合数据结构，可以获得比 n == int(sqrt(n)) ^ 2 更快的运行时间。

Python 算法示例如下：

class Solution: def numSquares(self, n): def is_divided_by(n, count): """ return: true if "n" can be decomposed into "count" number of perfect square numbers. e.g. n=12, count=3: true. n=12, count=2: false """ if count == 1: return n in square_nums for k in square_nums: if is_divided_by(n - k, count - 1): return True return False square_nums = set([i * i for i in range(1, int(n**0.5)+1)]) for count in range(1, n+1): if is_divided_by(n, count): return count Java 的示例如下： class Solution { Set<Integer> square_nums = new HashSet<Integer>(); protected boolean is_divided_by(int n, int count) { if (count == 1) { return square_nums.contains(n); } for (Integer square : square_nums) { if (is_divided_by(n - square, count - 1)) { return true; } } return false; } public int numSquares(int n) { this.square_nums.clear(); for (int i = 1; i * i <= n; ++i) { this.square_nums.add(i * i); } int count = 1; for (; count <= n; ++count) { if (is_divided_by(n, count)) return count; } return count; } }

④ 贪心 + BFS（广度优先搜索）

正如上述贪心算法的复杂性分析种提到的，调用堆栈的轨迹形成一颗 N 元树，其中每个结点代表 is_divided_by(n, count) 函数的调用。基于上述想法，可以把原来的问题重新表述如下：给定一个 N 元树，其中每个节点表示数字 n 的余数减去一个完全平方数的组合，我们的任务是在树中找到一个节点，该节点满足两个条件： (1) 节点的值（即余数）也是一个完全平方数。 (2) 在满足条件（1）的所有节点中，节点和根之间的距离应该最小。

在前面的方法 3 中，由于执行调用的贪心策略，实际上是从上到下逐层构造 N 元树。以 BFS（广度优先搜索）的方式遍历它。在 N 元树的每一级，都在枚举相同大小的组合。遍历的顺序是 BFS，而不是 DFS（深度优先搜索），这是因为在用尽固定数量的完全平方数分解数字 n 的所有可能性之前，不会探索任何需要更多元素的潜在组合。算法思路分析： 首先，我们准备小于给定数字 n 的完全平方数列表（即 square_nums）。然后创建 queue 遍历，该变量将保存所有剩余项在每个级别的枚举。在主循环中，迭代 queue 变量。在每次迭代中，检查余数是否是一个完全平方数。如果余数不是一个完全平方数，就用其中一个完全平方数减去它，得到一个新余数，然后将新余数添加到 next_queue 中，以进行下一级的迭代。一旦遇到一个完全平方数的余数，就会跳出循环，这也意味着找到了解。 在典型的 BFS 算法中，queue 变量通常是数组或列表类型。但是，这里使用 set 类型，以消除同一级别中的剩余项的冗余。事实证明，这个小技巧甚至可以增加 5 倍的运行加速。以 numSquares(7) 为例说明队列的布局： Python 算法如下： class Solution: def numSquares(self, n): # list of square numbers that are less than `n` square_nums = [i * i for i in range(1, int(n**0.5)+1)] level = 0 queue = {n} while queue: level += 1 #! Important: use set() instead of list() to eliminate the redundancy, # which would even provide a 5-times speedup, 200ms vs. 1000ms. next_queue = set() # construct the queue for the next level for remainder in queue: for square_num in square_nums: if remainder == square_num: return level # find the node! elif remainder < square_num: break else: next_queue.add(remainder - square_num) queue = next_queue return level Java 算法如下： class Solution { public int numSquares(int n) { ArrayList<Integer> square_nums = new ArrayList<Integer>(); for (int i = 1; i * i <= n; ++i) { square_nums.add(i * i); } Set<Integer> queue = new HashSet<Integer>(); queue.add(n); int level = 0; while (queue.size() > 0) { level += 1; Set<Integer> next_queue = new HashSet<Integer>(); for (Integer remainder : queue) { for (Integer square : square_nums) { if (remainder.equals(square)) { return level; } else if (remainder < square) { break; } else { next_queue.add(remainder - square); } } } queue = next_queue; } return level; } }