LeetCode 完全平方数问题：递归解法中移除内层循环的正确实现-js教程-PHP中文网

LeetCode 完全平方数问题：递归解法中移除内层循环的正确实现

本文详解如何在完全平方数问题的递归解法中安全移除显式 for 循环，指出原尝试中“状态设计错误”“边界判断顺序不当”“缓存未使用”三大核心问题，并提供修正后的高效记忆化递归实现。

本文详解如何在完全平方数问题的递归解法中安全移除显式 for 循环，指出原尝试中“状态设计错误”“边界判断顺序不当”“缓存未使用”三大核心问题，并提供修正后的高效记忆化递归实现。

在 LeetCode 279. Perfect Squares 问题中，目标是求组成正整数 n 所需的最少完全平方数个数（如 12 = 4 + 4 + 4 → 返回 3）。经典递归解法通常用一个 for 循环枚举所有可能的平方数 i² ≤ n，但有开发者试图通过引入额外状态变量 ind（表示当前考虑的平方根索引）来“展开循环”，改用两个分支（取/不取 ind²）模拟搜索过程。这种思路可行，但实现细节极易出错。

关键问题在于状态定义与转移逻辑是否完备：

❌ 错误：dfs(num - ind*ind, ind+1) 强制跳过当前 ind，导致同一平方数（如 4）无法重复使用，而题目允许重复使用（12 = 4 + 4 + 4 合法）。
❌ 错误：if (num === 0) return 0 放置在 if (ind > sqrt(num)) 之后，可能导致 num === 0 未被及时捕获，提前返回 Infinity。
❌ 错误：声明了 const hash = {} 却全程未读写，失去记忆化意义，时间复杂度退化为指数级，必然超时。

✅ 正确做法是：

将 num === 0 作为最高优先级基础情况；
使用 ind * ind > num 替代 Math.sqrt()，避免浮点误差与性能损耗；
在“取”分支中保持 ind 不变：dfs(num - ind*ind, ind)，确保可重复选取同一平方数；
严格使用缓存：以 num 为键（注意：此处状态仅依赖 num，ind 是搜索顺序控制变量，不影响最小解——因我们总从 1 开始尝试，且允许重复，故 dfs(num) 的最优解与 ind 起始值无关；实际可简化为单参数记忆化）。

以下是修正后的完整实现：

ZeroClaw

一款AI工具，主要用于开源、轻量级 AI Agent 框架，基于 Rust 语言编写，适合需要提升相关任务效率的用户。

下载

var numSquares = function(n) {
    const cache = {};

    const dfs = (num, ind) => {
        if (num  num) return Infinity;

        // 分支1：跳过 ind²，尝试更大的平方数
        const n_take = dfs(num, ind + 1);
        // 分支2：选用 ind²（可重复），num 减去该值，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);
};

⚠️ 注意事项：

本解法虽移除了显式 for，但本质仍是对平方数集合的回溯搜索，时间复杂度仍为 O(n√n)，优于暴力但弱于标准 DP（O(n√n) vs O(n√n) 理论一致，但常数更优）；
若追求极致效率，推荐使用动态规划：dp[i] = min(dp[i - j*j] + 1)，或数学解法（四平方定理 + 三平方判定）；
缓存键应为 num 而非 [num, ind]：因 dfs(num) 的最优解不依赖 ind 的初始值（只要 ind=1 开始且允许重复，覆盖全部组合），过度缓存反而增加空间开销。