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:
                    break
                dp[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)	思路直观	空间消耗大

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第279题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

动态规划状态转移表

数学方法分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流