LeetCode完美平方数问题：移除递归循环出错求助

我正在解决LeetCode上的完美平方数问题，以下是一种带缓存的递归解法：

function rc (n, cache = {}) {
    if (n <= 0) return 0;
    if (cache[n] !== undefined) return cache[n]
    let min = Infinity;
    for (let i = 1; i * i <= n; i++) {
        min = Math.min(1 + rc(n - i * i, cache), min);
    }
    return cache[n] = min;
}

我尝试移除该解法中的for循环，但改写后的DFS代码存在问题，想请教是否存在可行的移除循环的方法，我的改写代码如下：

var numSquares = function(n) {
    const hash = {};
    let min = Infinity;

    const dfs = (num, ind) => {
        // * b: base (bad)
        if(num < 0) return Infinity;

        // * b: base (bound)
        const half_num = Math.floor(Math.sqrt(num));
        if(ind > half_num) return Infinity;

        // * b: base (good)
        if(num === 0) return 0;

        // * b: state: num and ind
        // * b: decision
        const n_take = dfs(num, ind+1);
        const take = 1 + dfs(num - ind*ind, ind+1);

        min = Math.min(n_take, take);
          
        return min;
    }

    // * b: state: num
    const res = dfs(n, 1);
    return res;
};

问题分析 #

你改写的DFS代码有几个核心问题：

• 全局变量min会被递归的不同分支覆盖，导致最终结果错误；
• 没有对(num, ind)这个状态做缓存，会产生大量重复计算，效率极低；
• 决策逻辑偏差：原解法允许重复选取同一个平方数（比如n=4可以用两个2²），但你的代码选完当前平方数后直接跳到下一个，限制了重复选取的可能。

可行的移除循环的DFS写法 #

要移除for循环，我们可以把“遍历所有平方数”转化为递归的分支选择：对于当前剩余数值num和当前考虑的平方数索引ind，有两种选择：不选当前平方数，直接跳到下一个，或者选当前平方数，继续考虑当前平方数（支持重复选取）。同时给(num, ind)状态加缓存，避免重复计算。

var numSquares = function(n) {
    // 预计算所有不超过n的平方数
    const squares = [];
    for (let i = 1; i * i <= n; i++) {
        squares.push(i * i);
    }
    const cache = new Map();

    const dfs = (num, ind) => {
        // 基准情况：剩余数值为0，不需要更多平方数
        if (num === 0) return 0;
        // 基准情况：所有平方数都遍历完，无法凑出剩余数值
        if (ind >= squares.length) return Infinity;
        // 检查缓存，避免重复计算相同状态
        const key = `${num}-${ind}`;
        if (cache.has(key)) return cache.get(key);

        // 分支1：不选当前平方数，直接处理下一个
        const notTake = dfs(num, ind + 1);
        // 分支2：选当前平方数（需保证当前平方数不超过剩余数值），继续考虑当前平方数（支持重复选）
        const take = squares[ind] <= num ? 1 + dfs(num - squares[ind], ind) : Infinity;

        // 取两个分支的最小值，存入缓存后返回
        const minCount = Math.min(notTake, take);
        cache.set(key, minCount);
        return minCount;
    }

    return dfs(n, 0);
};

说明 #

• 预计算squares数组，避免递归过程中重复计算平方数，提升效率；
• 用(num, ind)作为缓存key，这两个参数唯一确定当前递归状态；
• 分支逻辑完全匹配原递归解法的重复选取规则；
• 移除全局变量min，让每个递归分支独立计算最小值，避免结果被覆盖。

内容的提问来源于stack exchange，提问作者kenpeter