LeetCode 279. 完全平方数

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

题目描述

✅ 279. 完全平方数

image-20260928204543826

题意分析

把正整数 n 写成若干正完全平方数之和，求使用的最少项数。完全平方数形如 j * j，其中 j >= 1；同一个平方数可以重复使用。

返回的是最少数量，不是具体拆法，也不是方案总数。因为一也是平方数，任何正整数都能表示，因此一定有答案；但优先选最大的平方数并不能保证剩余部分所需的项数最少。

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

核心思路

[!blue]

不同选择可能留下相同的剩余目标，而后续需要的最少数量只与这个剩余值有关，与前面如何选择无关。因此定义 dp[i] 为恰好凑出和 i 所需的最少平方数个数，保存每个较小目标的最优结果。

对凑出 i 的任意方案，取其中最后一个平方数 j * j，其余部分必须凑出 i - j * j。这一部分最少需要 dp[i - j * j] 项，加上当前平方数，就得到候选 dp[i - j * j] + 1。

所有方案的最后一项都在满足 j * j <= i 的平方数中，枚举这些候选便不会遗漏。最优方案的剩余部分也必须最优，否则换成更少项的拆法就能让整个方案更优。因此取所有候选的最小值就是 dp[i]。

边界 dp[0] = 0 表示凑出零不需要选任何项，使目标本身为平方数时能正确得到一项。对正目标，先令 dp[i] = i，对应全部使用平方数一，是一个一定可行的上界。

每个转移都依赖严格小于 i 的下标，所以按 i 从小到大计算即可。剩余目标的最优解可以再次使用同一个平方数，重复使用的要求由这种转移自然实现，无需记录使用次数。

解题步骤

  1. 创建长度为 n + 1 的数组，保留 dp[0] = 0。
  2. 从 i = 1 到 n 依次计算，先将 dp[i] 设为全部使用一时的数量 i。
  3. 枚举 j >= 1 且 j * j <= i，令 dp[i] = min(dp[i], dp[i - j * j] + 1)。
  4. 每个目标都取完所有最后一项的候选后，最终返回 dp[n]。

代码实现

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]。

关键点总结

[!green]

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

易错点总结

[!yellow]

  • 条件必须包含 j * j == i，否则目标恰好为平方数时会漏掉直接使用一项的方案。
  • 除 dp[0] 外，不能直接拿默认零取最小值；应先设为可行上界，再逐步优化。
  • 枚举不同平方数时需要取最小值，直接覆盖会丢掉前面更优的候选。
  • 目标值要从小到大计算，反向填表时依赖状态尚未求出。
  • 优先选较大平方数只能减少当次余数，不能保证整个拆法项数最少，应比较完整候选。

相似题目

题目 难度 关联与区别
322. 零钱兑换 中等 把硬币面额设为不超过n的完全平方数，就得到相同的最少项数DP。
518. 零钱兑换 II 中等 按金额或目标长度累积可重复选择的结果；本题候选值为完全平方数，该题先枚举硬币以统计无序组合。
377. 组合总和 Ⅳ 中等 按金额或目标长度累积可重复选择的结果；本题候选值为完全平方数，该题先枚举目标以统计有序方案。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/70176092
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！