# 如何解决LeetCode中完全平方数的问题 ## 问题描述 LeetCode中的[279. 完全平方数](https://leetcode.com/problems/perfect-squares/)问题要求我们找到最少数量的完全平方数（如1, 4, 9, 16等），使得它们的和等于给定的正整数n。例如： - 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 - 输入：n = 13 输出：2 解释：13 = 4 + 9 这个问题看似简单，但涉及动态规划、数学定理等核心算法思想。下面我们将逐步分析解决方案。 ## 方法一：动态规划（基础版） ### 核心思想 动态规划是解决此类"最少数量组合"问题的经典方法。我们定义`dp[i]`表示组成数字i所需的最少完全平方数数量。 ### 算法步骤 1. 初始化`dp`数组，长度为`n+1`，`dp[0] = 0`（因为0不需要任何平方数） 2. 对于每个数字`i`从1到n： - 初始化`dp[i]`为最大值（因为最坏情况是全部用1相加） - 遍历所有可能的平方数`j*j`（其中`j*j <= i`）： - `dp[i] = min(dp[i], dp[i - j*j] + 1)` 3. 返回`dp[n]` ### Python实现 ```python def numSquares(n): dp = [float('inf')] * (n + 1) dp[0] = 0 for i in range(1, n + 1): j = 1 while j * j <= i: dp[i] = min(dp[i], dp[i - j*j] + 1) j += 1 return dp[n] 将问题转化为图的最短路径问题，每个数字代表一个节点，如果两个数字相差一个完全平方数，则存在边连接。
from collections import deque def numSquares(n): squares = [i*i for i in range(1, int(n**0.5)+1)] queue = deque([(0, 0)]) visited = set() while queue: current, steps = queue.popleft() for square in squares: new_sum = current + square if new_sum == n: return steps + 1 if new_sum < n and new_sum not in visited: visited.add(new_sum) queue.append((new_sum, steps + 1)) 根据拉格朗日四平方定理，任何自然数都可以表示为最多4个完全平方数的和。因此答案只能是1、2、3或4。
def numSquares(n): def is_square(x): return int(x**0.5)**2 == x # 情况1：n是完全平方数 if is_square(n): return 1 # 情况2：检查4^k*(8m+7) temp = n while temp % 4 == 0: temp //= 4 if temp % 8 == 7: return 4 # 情况3：检查两个平方数之和 for i in range(1, int(n**0.5)+1): if is_square(n - i*i): return 2 # 情况4：其他情况 return 3 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 动态规划 | O(n√n) | O(n) | 通用解法，易于理解 |
| BFS | O(n^(h/2)) | O(n) | 适合求最短路径问题 |
| 数学方法 | O(√n) | O(1) | 大数时效率最高 |
推荐选择策略： 1. 面试中优先实现动态规划（展示基础能力） 2. 竞赛或优化场景使用数学方法 3. BFS可作为替代思路展示
int(n**0.5)+1而非n//2完全平方数问题展示了多种算法思想的典型应用： - 动态规划解决最优化问题 - BFS处理最短路径问题 - 数学定理提供理论保证
掌握这道题的多种解法，能够显著提升对算法问题的综合理解能力。建议读者先实现动态规划版本，再尝试其他方法，最后比较不同方法的性能差异。 “`
该文章提供了三种解决方案的详细说明、代码实现和复杂度分析，并包含方法对比和常见错误提示，总字数约1350字。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
