【数据结构与算法】之组成和的完全平方数最少个数的求解思路与算法示例
【摘要】
一、题目要求
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例一
输入: n = 12
输出: 3
...
一、题目要求
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
- 示例一
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4
- 1
- 2
- 3
- 示例二
输入: n = 13
输出: 2
解释: 13 = 4 + 9
- 1
- 2
- 3
二、示例算法
① 暴力枚举法 [超出时间限制]
- 这个问题要求我们找出由完全平方数组合成给定数字的最小个数。我们将问题重新表述成：
给定一个完全平方数列表和正整数 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)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 上面的解决方案可以适用于较小的正整数 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]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 那么 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];
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 复杂度分析
- 时间复杂度：O(n⋅ n \sqrt{n} n)，在主步骤中有一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 n \sqrt{n} 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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
④ 贪心 + 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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/Forever_wj/article/details/109193291
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）