复盘 · LC 279 完全平方数

题目

题号：LeetCode 279
名称：完全平方数（Perfect Squares）
难度：Medium
链接：leetcode.cn/problems/perfect-squares
今日代码：279-完全平方数/index.js

题意

给定正整数 n，把它写成若干完全平方数之和，求所需最少的平方数个数。

例：12 = 4 + 4 + 4 → 3 个；13 = 4 + 9 → 2 个。
数学上拉格朗日四平方定理保证有解；算法上要算最少个数。
边界：n = 1 答 1；完全平方数本身答 1。

涉及算法

标签	一句话
一维 DP	`dp[i]` = 和为 i 的最少平方数个数
完全背包味道	每种平方数 `j²` 可用无限次
BFS（备选）	把「减一个平方数」看成层数 +1 的最短路

教程对照：状态定义与 21 · DP 入门 · 一维中 322 零钱兑换同族——dp[i] = min(dp[i], dp[i - j²] + 1)。

评价我的解法

注释写「dp 还是好难」「借鉴大神题解」——代码是标准 DP 完全背包，逻辑无误，但性能在本题数据下偏弱（199 ms，击败约 9%）。

我的代码（摘自 279-完全平方数/index.js，不含测例）：

javascript

var numSquares = function (n) {
  const dp = Array.from({ length: n + 1 }).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
};

对在哪

初值正确：dp[0] = 0，其余 Infinity，与 322 同一套路。
转移对：枚举 j，用 j² 当「硬币面额」，完全背包内层循环写法成立。
边界：j = 0 时 dp[i - 0] + 1 不会误改最优（dp[i] 至少为 1），不会破坏正确性。

糙在哪

循环起点：外层 i 从 0 开始多算一轮；可从 i = 1 起，语义更干净。
性能：O(n · √n) 的 DP 在本题常数偏大；BFS 或数学优化（四平方定理预处理）往往更快——说明「会写 DP」和「知道这题更像最短路」之间还有一层。
独立推导：注释暴露仍依赖题解，面试要先能说出「为什么 dp[i] 取 min」。

小结：DP 版能 AC 且结构标准，适合作为与 322 配对的模板；下一步 worth 默写 BFS 版，加深「最少步数 = 层序 BFS」直觉。

最佳题解

BFS（最少步数直觉）——把每个 n 看成状态，一步减掉任意 j²：

javascript

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  const queue = [n];
  const visited = new Set([n]);
  let steps = 0;

  while (queue.length) {
    const size = queue.length;
    steps++;
    for (let t = 0; t < size; t++) {
      const cur = queue.shift();
      for (let j = 1; j * j <= cur; j++) {
        const next = cur - j * j;
        if (next === 0) return steps;
        if (!visited.has(next)) {
          visited.add(next);
          queue.push(next);
        }
      }
    }
  }
  return steps;
};

时间约 O(n · √n)（ visits 有界），空间 O(n)。
为何有时更优：题目问「最少个数」，等价于无权图最短路；BFS 一层即一步，和 11 · 队列与层序对齐。DP 版仍应保留，与 322 统一写法。

关联题目

题	为何相关
322. 零钱兑换	同一完全背包 DP 框架（今日同练）
139. 单词拆分	`dp[i]` 能否由字典拼出，布尔版背包
743. 网络延迟时间	「最少步数/层数」也可 Dijkstra / BFS 建模

一句话带走

完全平方数：把每个 j² 当无限硬币，dp[i] = min(dp[i], dp[i-j²]+1)；或 BFS 一层减一个平方直到 0。

复盘 · LC 279 完全平方数 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​