当前位置：首页 > news >正文

LeetCode第279题_完全平方数

news 2025/6/22 11:09:04

LeetCode 第279题：完全平方数

📖 文章摘要

本文详细解析LeetCode第279题"完全平方数"，这是一道经典的动态规划问题。文章提供了动态规划和数学方法两种解题思路，包含C#、Python、C++三种语言实现，配有详细的状态转移表格和性能对比。适合学习动态规划和数学优化的读者。

核心知识点： 动态规划、完全平方数、数学定理
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升动态规划技能的开发者

题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示

1 <= n <= 10^4

解题思路

本题可以使用动态规划来解决，也可以使用数学方法。我们主要介绍这两种方法：

动态规划方法：
- 定义dp[i]表示数字i最少需要多少个完全平方数
- 对于每个数i，枚举所有小于等于i的完全平方数j*j
- 状态转移方程：dp[i] = min(dp[i], dp[i - j*j] + 1)
数学方法（四平方和定理）：
- 任何正整数都可以表示为至多4个平方数之和
- 当且仅当n≠4^k(8m+7)时，n可以表示为至多3个平方数之和

图解思路

动态规划状态转移表

数字n	可用平方数	dp[n]	组成方式	说明
1	1	1	1	基础情况
2	1	2	1+1	只能用1
3	1	3	1+1+1	只能用1
4	1,4	1	4	可以直接用4
5	1,4	2	4+1	使用4和1
12	1,4,9	3	4+4+4	使用三个4
13	1,4,9	2	4+9	使用4和9

数学方法分析表

情况	条件	结果	示例	说明
完全平方数	n = k^2	1	16=4^2	直接是平方数
两个平方数和	n = a^2 + b^2	2	13=4+9	可以分解为两个平方数之和
三个平方数和	n ≠ 4^k(8m+7)	3	12=4+4+4	可以分解为三个平方数之和
四个平方数和	其他情况	4	7=4+1+1+1	需要四个平方数

代码实现

C# 实现

public class Solution {public int NumSquares(int n) {// 创建dp数组，初始值设为最大可能值int[] dp = new int[n + 1];Array.Fill(dp, int.MaxValue);dp[0] = 0;// 计算所有小于等于n的完全平方数int maxSquareRoot = (int)Math.Sqrt(n);int[] squares = new int[maxSquareRoot];for (int i = 1; i <= maxSquareRoot; i++) {squares[i - 1] = i * i;}// 动态规划过程for (int i = 1; i <= n; i++) {for (int j = 0; j < maxSquareRoot && squares[j] <= i; j++) {dp[i] = Math.Min(dp[i], dp[i - squares[j]] + 1);}}return dp[n];}
}

Python 实现

class Solution:def numSquares(self, n: int) -> int:# 创建dp数组dp = [float('inf')] * (n + 1)dp[0] = 0# 计算所有小于等于n的完全平方数squares = [i * i for i in range(1, int(n ** 0.5) + 1)]# 动态规划过程for i in range(1, n + 1):for square in squares:if square > i:breakdp[i] = min(dp[i], dp[i - square] + 1)return dp[n]

C++ 实现

class Solution {
public:int numSquares(int n) {// 创建dp数组vector<int> dp(n + 1, INT_MAX);dp[0] = 0;// 计算所有小于等于n的完全平方数int maxSquareRoot = (int)sqrt(n);vector<int> squares(maxSquareRoot);for (int i = 1; i <= maxSquareRoot; i++) {squares[i - 1] = i * i;}// 动态规划过程for (int i = 1; i <= n; i++) {for (int j = 0; j < maxSquareRoot && squares[j] <= i; j++) {dp[i] = min(dp[i], dp[i - squares[j]] + 1);}}return dp[n];}
};

执行结果

C# 实现

执行用时：84 ms
内存消耗：27.8 MB

Python 实现

执行用时：148 ms
内存消耗：15.2 MB

C++ 实现

执行用时：44 ms
内存消耗：9.1 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	27.8 MB	代码结构清晰，性能适中
Python	148 ms	15.2 MB	代码最简洁，但运行较慢
C++	44 ms	9.1 MB	性能最优，内存占用最小

代码亮点

🎯 使用动态规划优化时间复杂度
💡 预计算完全平方数数组，避免重复计算
🔍 使用Math.Min/min优化比较操作
🎨 代码结构清晰，变量命名直观

常见错误分析

🚫 未初始化dp数组为最大值
🚫 完全平方数计算范围错误
🚫 状态转移方程写错
🚫 边界条件处理不当

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
动态规划	O(n * sqrt(n))	O(n)	通用性强	空间消耗大
数学方法	O(sqrt(n))	O(1)	速度快	需要数学知识
BFS	O(n * sqrt(n))	O(n)	思路直观	空间消耗大