279. 完全平方数 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/perfect-squares/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数 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
题目详细分析
- 数据范围：n <= 10^4，完全平方数有 sqrt(10^4) = 100 个（1², 2², …, 100²）。
- 核心约束：每个完全平方数可以无限次使用（因为 4=1+1+1+1 也合法），这是一个完全背包问题。
- 边界条件：n=1 时最少 1 个（1=1²）；n 本身就是完全平方数时最少为 1。
- 隐藏条件：从数学上，根据四平方和定理，任何正整数都可以表示为不超过 4 个完全平方数之和。但本题仍需计算精确最小值。
小白版直白理解
你要用”完全平方数”（1,4,9,16,25,…）来拼成一个目标数字 n，就像用不同面值的硬币凑钱。每个”硬币”可以重复使用，你想让使用的硬币数量最少。比如要凑 12，用三个 4 比用 12 个 1 好。这就是”最少硬币”问题，只不过硬币面额是平方数。
解题思路
思路一：完全背包 DP（推荐）
核心洞察：将 1², 2², …, 100² 视为物品，每个可以无限使用，目标是凑成和 n。对于每个金额 i，尝试减去一个平方数 j²，看剩下 i-j² 的最优解 + 1。
DP 五步法：
- dp 定义：
dp[i]表示和为 i 的完全平方数的最少个数 - 递推公式：
dp[i] = min(dp[i], dp[i - j*j] + 1)，j 从 1 到 sqrt(i) - 初始化：
dp[0] = 0，dp[1..n] = inf（或一个很大的数） - 遍历顺序：从 i=1 到 n 正序（完全背包允许重复选取）
- 举例验证：n=12 → dp[0]=0, dp[1]=1, dp[2]=2, …, dp[4]=1, dp[8]=2, dp[12]=min(dp[11]+1, dp[8]+1, dp[3]+1)=min(3+1,2+1,3+1)=3 ✓
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]思路二：BFS 最短路径
将问题转化为图：每个数字 i 可以走到 i - j²（j² <= i）。求从 n 走到 0 的最短步数。
from collections import deque
def numSquares(n):
queue = deque([(n, 0)]) # (当前值, 步数)
visited = [False] * (n + 1)
visited[n] = True
while queue:
num, step = queue.popleft()
j = 1
while j * j <= num:
nxt = num - j * j
if nxt == 0:
return step + 1
if not visited[nxt]:
visited[nxt] = True
queue.append((nxt, step + 1))
j += 1
return 0思路三：数学定理法（四平方和定理）
根据四平方和定理 + 勒让德三平方定理，可以 O(sqrt(n)) 判断。
def numSquares(n):
# 本身是平方数
if int(n ** 0.5) ** 2 == n:
return 1
# 检查 4^k(8m+7) 形式 → 答案为 4
temp = n
while temp % 4 == 0:
temp //= 4
if temp % 8 == 7:
return 4
# 检查是否两个平方数和
for i in range(1, int(n ** 0.5) + 1):
if int((n - i * i) ** 0.5) ** 2 == n - i * i:
return 2
return 3易错点
- dp 数组大小：dp 长度为 n+1，初始化
dp[0]=0是关键基础。 - 内层循环范围：
j*j <= i而不是j*j <= n，否则会出现减出负数的情况。 - inf 设置：推荐
float('inf')或n + 1，不要用10**9等可能导致相加溢出的值。 - 完全背包遍历顺序：一维 dp 用正序遍历（与 0-1 背包区分）。
框架提炼
完全背包求最小值模板：
def complete_knapsack_min(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1): # 遍历背包容量
for coin in coins: # 遍历物品
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1关键点：正序遍历容量（保证物品可重复取），dp[0] 初始化为 0，其余为 inf。
关联题目
- 322-零钱兑换 — 完全背包的经典形式，思路完全一致
- 416-分割等和子集 — 0-1 背包变体，注意与完全背包的区分
- 139-单词拆分 — 完全背包的字符串版本