动态规划解决完全平方数问题：LeetCode 279题详解

1. 问题背景与核心思路

这道LeetCodeHot100的279题"完全平方数"看似简单，实则暗藏玄机。题目要求找出和为n的完全平方数的最少数量，比如12=4+4+4，最少需要3个平方数。乍一看像是数学题，但用纯数学方法（如四平方和定理）解题会错过算法训练的要点。

我最初尝试用贪心算法，每次都取最大可能的平方数，很快就发现有问题。比如12按贪心会得到9+1+1+1=4个，显然不如4+4+4=3个更优。这时候才意识到这其实是个背包问题的变种：

• 背包容量：目标数字n
• 物品：所有≤n的完全平方数（1,4,9...）
• 物品价值：每个平方数计数为1（求最小数量）
• 每个物品可以重复选取（完全背包）

2. 动态规划解法详解

2.1 状态定义与转移方程

定义dp[i]表示组成数字i所需的最少完全平方数数量。初始化dp[0]=0，其他设为无穷大。

转移方程：

for j in range(1, int(math.sqrt(i)) + 1): dp[i] = min(dp[i], dp[i - j*j] + 1)

这个方程的意思是：对于每个i，我们尝试所有可能的平方数jj（j从1到√i），看看用i-jj的结果加上当前这个平方数（计数+1）是否能得到更优解。

2.2 完整代码实现

import math def numSquares(n): dp = [float('inf')] * (n + 1) dp[0] = 0 for i in range(1, n + 1): for j in range(1, int(math.sqrt(i)) + 1): dp[i] = min(dp[i], dp[i - j*j] + 1) return dp[n]

时间复杂度O(n√n)，空间复杂度O(n)。在LeetCode上实测可以AC，但还有优化空间。

3. 数学优化思路

3.1 四平方和定理

任何自然数都可以表示为不超过4个整数的平方和。这意味着答案只可能是1、2、3或4。我们可以利用这个性质提前返回：

1. 如果n本身就是完全平方数，返回1
2. 如果n可以表示为两个平方数之和，返回2
3. 如果n满足n=4^k*(8m+7)的形式，返回4（根据拉格朗日定理）
4. 其他情况返回3

3.2 优化后的代码

def numSquares(n): def is_square(x): sq = int(math.sqrt(x)) return sq*sq == x if is_square(n): return 1 # 检查是否可以表示为两个平方数之和 for i in range(1, int(math.sqrt(n)) + 1): if is_square(n - i*i): return 2 # 检查是否符合4^k*(8m+7)的形式 while n % 4 == 0: n //= 4 if n % 8 == 7: return 4 return 3

这个版本时间复杂度降到了O(√n)，空间复杂度O(1)，性能大幅提升。

4. BFS解法与比较

4.1 广度优先搜索思路

把这个问题看作图的最短路径问题：

• 节点：当前数字
• 边：减去一个平方数的操作
• 目标：从n到0的最短路径

from collections import deque def numSquares(n): squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)] queue = deque([(n, 0)]) visited = set() while queue: num, step = queue.popleft() for square in squares: if num - square == 0: return step + 1 if num - square > 0 and (num - square) not in visited: visited.add(num - square) queue.append((num - square, step + 1)) return -1

4.2 各方法对比

5. 常见错误与调试技巧

5.1 典型错误案例

1. 贪心算法陷阱：

   # 错误示范 def numSquares(n): count = 0 while n > 0: largest = int(math.sqrt(n))**2 n -= largest count += 1 return count

   对于n=12会得到错误答案4（9+1+1+1）

2. DP数组初始化错误： 忘记初始化dp[0]=0，或者初始值设得太小导致min比较失效

3. 平方数范围错误： 计算j的范围时错误地用了n而不是i的平方根

5.2 调试建议

1. 打印DP表观察状态转移：

   print(f"dp[{i}] = min({dp[i]}, {dp[i - j*j]} + 1)")

2. 小规模测试用例验证：

   • n=1 → 1
   • n=2 → 2（1+1）
   • n=13 → 2（9+4）

3. 边界条件检查：

   • n=0应该返回0
   • n=10^4（最大边界值）

6. 实际应用与变种问题

6.1 实际问题中的应用

这种"数字分解"问题在实际中有很多应用场景：

• 货币找零问题（面额是平方数）
• 资源分配的最优组合
• 游戏中的道具合成系统

6.2 相关变种题目

1. Coin Change（LeetCode 322）： 把平方数换成任意面额的硬币

2. Perfect Squares进阶版： 限制使用的平方数种类，比如只能用特定几个平方数

3. Combination Sum（LeetCode 39）： 找出所有可能的组合而不只是最小数量

7. 性能优化实战

对于特别大的n（比如10^6级），我们可以进一步优化DP解法：

1. 预处理平方数：

   squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]

2. 反向遍历平方数：

   for s in reversed(squares): if s > i: continue dp[i] = min(dp[i], dp[i - s] + 1)

3. 提前终止：

   if dp[i] == 1: break # 已经是最优解

实测这些优化可以让DP解法在n=10^6时仍能快速运行（<1秒）。

8. 不同语言实现要点

8.1 Java实现注意点

// 注意整数溢出问题 for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); }

8.2 C++实现技巧

// 使用静态数组缓存平方数 static vector<int> dp{0}; while (dp.size() <= n) { int m = dp.size(); int cnt = INT_MAX; for (int j = 1; j * j <= m; ++j) { cnt = min(cnt, dp[m - j * j] + 1); } dp.push_back(cnt); }

8.3 JavaScript的坑

// 注意JS的数字精度问题 let dp = new Array(n+1).fill(Infinity); dp[0] = 0;

9. 学习路线建议

要系统掌握这类问题，建议的学习路径：

1. 先掌握基础背包问题（01背包、完全背包）
2. 理解动态规划的基本套路（状态定义、转移方程）
3. 练习相关变种问题：
   • Coin Change系列
   • 分割等和子集
   • 目标和问题
4. 学习数学优化方法（数论基础）
5. 尝试用图论视角重新理解问题

10. 面试考点分析

这道题在面试中常考察：

1. 能否识别出背包问题的变种
2. 动态规划的实现能力
3. 边界条件处理
4. 优化意识（从O(n√n)到O(√n)）

常见follow-up问题：

• 如果限制只能使用某些特定平方数怎么办？
• 如何输出具体的平方数组合而不仅仅是数量？
• 如果n非常大（比如10^12）该如何优化？

11. 个人实战心得

在多次刷这道题后，我总结出几点经验：

1. 先写暴力解法再优化：不要一开始就追求最优解，先确保正确性

2. 画状态转移表：对于DP问题，手动画几个case的DP表能极大帮助理解

3. 数学知识很重要：了解一些基础数论知识（如四平方和定理）能打开思路

4. 测试用例要全面：特别注意边界值（0、1、完全平方数、大数）

5. 比较不同解法：同一问题用DP、BFS、数学方法分别实现，加深理解

最后分享一个实用技巧：在LeetCode做题时，可以先看输入约束。这道题n≤10^4，意味着O(n√n)≈10^6的解法完全够用，不必一开始就追求数学最优解。