本文详解 leetcode「完全平方数」问题中递归解法的常见误区，重点分析移除 for 循环时因状态设计不当导致的重复使用限制、边界判断顺序错误及缓存缺失等关键问题，并提供修复后的高效记忆化 dfs 实现。
本文详解 leetcode「完全平方数」问题中递归解法的常见误区，重点分析移除 for 循环时因状态设计不当导致的重复使用限制、边界判断顺序错误及缓存缺失等关键问题，并提供修复后的高效记忆化 dfs 实现。
在解决 LeetCode 第 279 题「Perfect Squares」时，许多开发者尝试将标准的「枚举所有平方数 + 递归回溯」写法（含 for (i = 1; i*i 内层循环）重构为更“函数式”的双参数 DFS 形式——即用 <code>(num, ind) 表示“用 ≥ ind² 的平方数凑出 num 的最少个数”。这一思路方向正确，但实践中极易因状态语义理解偏差而引入逻辑错误。
核心问题有三：
重复使用限制错误：原代码中
dfs(num - ind*ind, ind+1)强制递归进入更大平方数，导致ind²只能用一次。而题目允许重复使用同一平方数（例如12 = 4 + 4 + 4），因此应改为dfs(num - ind*ind, ind)，保持ind不变以允许多次选取ind²。边界判断顺序不当：
if (num === 0) return 0被放在if (ind > Math.floor(Math.sqrt(num)))之后，可能导致num === 0未被及时捕获——尤其当ind已超界但num恰好为 0 时，会错误返回Infinity。正确做法是将num === 0作为最高优先级终止条件。缓存机制缺失：声明了
hash或cache却未实际使用，导致指数级重复计算，必然超时。记忆化必须基于num（而非num和ind的组合），因为对于相同剩余值num，无论当前ind如何，其最小组成数是唯一确定的（最优子结构决定）。
此外，还有两个工程细节值得优化：
- 避免调用
Math.sqrt(num)计算上界，改用ind * ind > num判断，既避免浮点误差，又提升性能； -
min变量应定义在dfs函数内部，避免闭包污染与作用域混乱。
以下是修正后的完整实现：
var numSquares = function(n) {
const cache = {};
const dfs = (num, ind) => {
if (num num) return Infinity; // ✅ 用乘法替代 sqrt
const skip = dfs(num, ind + 1); // 跳过 ind²
const take = 1 + dfs(num - ind * ind, ind); // ✅ ind 不变，支持重复使用
const min = Math.min(skip, take);
cache[num] = min; // ✅ 缓存以 num 为键的结果
return min;
};
return dfs(n, 1);
};
⚠️ 注意：该解法虽逻辑正确，但时间复杂度仍为 O(n√n)，略逊于标准动态规划（O(n√n) 但常数更小）或 BFS（最短路径视角，通常更快）。若追求极致效率，建议后续对比学习 DP 或 BFS 解法。但本实现的价值在于厘清 DFS 状态设计本质——num 是核心状态，ind 是搜索指针，缓存只需锚定 num。
