本文详解 leetcode「完全平方数」题中一种常见错误的递归改写——试图用双参数 dfs 替代原始平方根范围循环，指出其逻辑缺陷（重复使用限制、边界判断顺序、缓存缺失），并给出修复后的高效记忆化递归实现。
本文详解 leetcode「完全平方数」题中一种常见错误的递归改写——试图用双参数 dfs 替代原始平方根范围循环，指出其逻辑缺陷（重复使用限制、边界判断顺序、缓存缺失），并给出修复后的高效记忆化递归实现。
在解决 LeetCode 第 279 题「Perfect Squares」时，标准记忆化递归通常采用单状态 n + 内层 for (i = 1; i*i 枚举所有可能平方数的方式。有开发者尝试“消除内层循环”，转而引入双参数 DFS：<code>(num, ind)，意图将平方数枚举从显式循环转为递归分支（take vs n_take）。但该思路若未精准建模状态语义，极易引入逻辑错误。
核心问题在于 状态定义与转移的不匹配：
❌ 错误：
const take = 1 + dfs(num - ind*ind, ind+1)
此处ind+1强制跳过当前平方数ind²，导致同一平方数无法重复使用（如12 = 4 + 4 + 4中4被用了三次），而题目允许无限次使用任意完全平方数。正确做法是保持ind不变：dfs(num - ind*ind, ind)，表示“仍可继续选ind²”。❌ 错误：
if (num === 0) return 0放置位置过晚
若先检查if (ind * ind > num)，当num > 0但ind已越界时会直接返回Infinity，错过num === 0的合法终止。必须将num === 0作为最高优先级基础情况，紧随负数校验之后。❌ 错误：声明了
cache却未使用
无缓存的双参数 DFS 时间复杂度退化为指数级，必然超时。需在入口处查缓存，并在返回前写入cache[num] = min—— 注意：缓存键应为num（目标值），而非(num, ind)，因为ind仅控制搜索范围，真正决定子问题结果的是剩余数值num（最优子结构本质）。
此外，工程细节亦影响效率与可读性：
- 避免
Math.sqrt(num)：浮点运算开销大且有精度风险；改用ind * ind > num整数比较更安全高效； -
min变量应严格限定在dfs函数作用域内，避免闭包污染和意外状态共享。
✅ 修复后的完整实现如下（含关键注释）：
var numSquares = function(n) {
const cache = {};
const dfs = (num, ind) => {
// 基础情况1：无效状态
if (num num) return Infinity;
// 分支决策：
// n_take：跳过 ind²，尝试更大的平方数（ind+1）
const n_take = dfs(num, ind + 1);
// take：选用 ind²，剩余值减少，但 ind 不变（允许重复使用）
const take = 1 + dfs(num - ind * ind, ind);
// 合并结果并缓存
const min = Math.min(n_take, take);
cache[num] = min;
return min;
};
return dfs(n, 1);
};
? 关键总结：
- 消除显式循环本身可行，但必须确保状态空间覆盖完备性（允许重复选择）与子问题独立性（缓存键设计合理）；
- 双参数 DFS 中，
ind是搜索指针，num是核心状态；缓存num即可避免重复计算相同剩余值的所有路径； - 所有基础情况需按优先级排序：负数 → 零 → 越界，防止漏解；
- 此解法时间复杂度为
O(n√n)（每个num最多被√num个ind访问一次），空间复杂度O(n)，兼顾清晰性与效率，是理解动态规划状态转移思想的优质范例。
