LeetCode 279. 完全平方数

约 4 分钟
文章信息 13 个分类 8 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 20-50 字节跳动 美团 腾讯 滴滴 华为 商汤 LeetCode 热题 100
标签
动态规划 数学 广度优先搜索 背包问题 数学经典题 动态规划经典题 完全背包问题 完全背包
目录

题目描述

✅ 279. 完全平方数

image-20250420115115388

image-20250510232523413

题意分析

输入一个正整数 n，要输出一个数量：最少用几个完全平方数相加能凑出 n。注意求的是个数，不是具体是哪几个数，也不是有多少种凑法。

约束里有两个信号。第一，完全平方数可以重复使用，12 = 4 + 4 + 4 是合法的，所以这不是「每个数最多选一次」的选择问题。第二，n 的上界是 10^4，说明可以放心开一个和 n 同量级的数组，逐个数字把答案算出来。

边界方面，n 至少为 1，不存在 n = 0 的输入；1 本身就是完全平方数，所以任何 n 至少能用 n 个 1 凑出来，答案一定存在，不需要考虑无解的情况。这一点后面会直接用来做初始值。

解法：动态规划枚举平方数

核心思路

暴力搜索会反复计算同一个剩余值。比如不同选择顺序都可能走到「还差 8」，而从 8 到答案的最优结果与此前路径无关，因此可以把这些重叠子问题保存下来。

定义 dp[i] 为凑出 i 所需的最少平方数个数，dp[0] = 0。枚举最后选的平方数 j²，其前面必须是凑出 i - j² 的最优方案，因此有：

\[dp[i] = \min_{j^2 \le i}\{dp[i-j^2]+1\}\]

按 i 从小到大计算时，转移依赖的下标都小于 i。用归纳法看：假设更小金额的 dp 已最优，枚举最后一个平方数就覆盖了 i 的所有方案，取最小值后 dp[i] 也必然最优。初始令 dp[i] = i，表示最坏情况下使用 i 个 1，既保证状态可达，也避免无穷大溢出。

解题步骤

  1. 创建长度为 n + 1 的 dp，令 dp[0] = 0。
  2. 依次计算 i = 1..n，先用 dp[i] = i 作为「全用 1」的可行上界。
  3. 枚举所有满足 j * j <= i 的平方数，用 dp[i - j*j] + 1 更新最小值。
  4. 填表完成后返回 dp[n]。

以 n = 12 为例，平方数候选为 1、4、9。计算 dp[12] 时三种最后一步分别得到 dp[11]+1=4、dp[8]+1=3、dp[3]+1=4，所以答案为 3，对应 4 + 4 + 4。

代码实现

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) {
                // 枚举最后使用的平方数，转移到剩余数字。
                int square = j * j;
                dp[i] = Math.min(dp[i], dp[i - square] + 1);
            }
        }
        return dp[n];
    }
}

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = i
        for j := 1; j*j <= i; j++ {
            // 最后选择 j*j 后，问题变成凑出 i-j*j。
            square := j * j
            if dp[i-square]+1 < dp[i] {
                dp[i] = dp[i-square] + 1
            }
        }
    }
    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(n\sqrt{n})$。每个 i 枚举不超过 $\sqrt{i}$ 个平方数。
  • 空间复杂度：$O(n)$，用于保存 dp[0..n]。

关键点总结

  • 状态只由目标值决定，历史选择顺序无关，适合一维动态规划。
  • 枚举「最后一个平方数」可以无遗漏地覆盖所有方案。
  • dp[i] = i 是安全的可行上界，比无穷大哨兵更简单且不会加一溢出。
  • 必须按目标值递增填表，保证 dp[i - j*j] 已经是最优解。

易错点总结

  • 把条件写成 j*j < i：n = 4 时会漏掉平方数 4，无法得到答案 1。
  • 数组默认全为 0 却不设置 dp[i] 的上界：取最小值后所有状态都会错误保持 0。
  • 转移时直接覆盖而不取最小值：后枚举的平方数可能冲掉更优方案。
  • 从大到小计算 i：依赖状态尚未求出，dp[i] 不再具有最优含义。

相似题目

题目 难度 考察点
322. 零钱兑换 中等 面值由输入给定且可能凑不出，需要处理无解返回 -1
377. 组合总和 Ⅳ 中等 求的是顺序敏感的排列数，容量必须放外层循环
518. 零钱兑换 II 中等 求组合方案数，物品放外层循环才能避免重复计数
1449. 数位成本和为目标值的最大数字 困难 成本恰好用完的前提下比较字符串大小，还要回溯还原具体数字
LCR 103. 零钱兑换 中等 与 322 同型，重点在无解判定与初值哨兵的溢出处理
LCR 104. 组合总和 Ⅳ 中等 与 377 同型，重点在辨别题目问的是排列还是组合
面试题 08.11. 硬币 中等 固定四种面值求组合数，结果需要对 1000000007 取模