如何解决leetcode中完全平方数的问题

# 如何解决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]

复杂度分析

• 时间复杂度：O(n√n) —— 外层循环n次，内层循环最多√n次
• 空间复杂度：O(n) —— 需要存储dp数组

方法二：BFS（广度优先搜索）

核心思想

将问题转化为图的最短路径问题，每个数字代表一个节点，如果两个数字相差一个完全平方数，则存在边连接。

算法步骤

1. 创建队列，初始包含(0, 0)（当前和，步数）
2. 创建访问集合，记录已处理的数字
3. 当队列不为空时：
   • 弹出当前节点
   • 如果当前和等于n，返回步数
   • 遍历所有可能的平方数，将新和加入队列（如果未被访问）

Python实现

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))

复杂度分析

• 时间复杂度：O(n^(h/2))，h是最短路径长度
• 空间复杂度：O(n) —— 队列和访问集合的存储

方法三：数学方法（四平方定理）

核心定理

根据拉格朗日四平方定理，任何自然数都可以表示为最多4个完全平方数的和。因此答案只能是1、2、3或4。

算法步骤

1. 检查n是否是完全平方数（返回1）
2. 检查是否满足n = 4^k*(8m+7)（返回4）
3. 检查是否能表示为两个平方数之和（返回2）
4. 其他情况返回3

Python实现

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)
• 空间复杂度：O(1)

方法对比与选择

推荐选择策略： 1. 面试中优先实现动态规划（展示基础能力） 2. 竞赛或优化场景使用数学方法 3. BFS可作为替代思路展示

常见错误与陷阱

1. 未初始化dp[0]：会导致后续计算错误
2. 平方数生成范围错误：应使用int(n**0.5)+1而非n//2
3. BFS未剪枝：不记录已访问节点会导致重复计算
4. 数学方法条件顺序错误：必须先检查4平方的情况

总结

完全平方数问题展示了多种算法思想的典型应用： - 动态规划解决最优化问题 - BFS处理最短路径问题 - 数学定理提供理论保证

掌握这道题的多种解法，能够显著提升对算法问题的综合理解能力。建议读者先实现动态规划版本，再尝试其他方法，最后比较不同方法的性能差异。 “`

该文章提供了三种解决方案的详细说明、代码实现和复杂度分析，并包含方法对比和常见错误提示，总字数约1350字。