四面体顶点D出发n步返回路径计数：递归+记忆化优化求助

原递归暴力枚举所有路径，n较大时（比如15）效率极低，因为每一步有3种可选方向，时间复杂度达O(3^n)。要改成递归+记忆化，核心是抓住重复计算的状态：当前所在的顶点、剩余需要走的步数——这两个参数完全决定了后续的路径数，无需记录完整路径。

实现思路 #

定义递归函数countPaths(current, remaining)，表示从current顶点出发，走remaining步后回到D的路径数：

1. 终止条件：
   • 剩余步数为0时，只有当前顶点是D才算有效路径，返回1；否则返回0。
   • 剩余步数为1时，当前不是D的话，有1条直接回D的路径；当前是D的话无法停在原地，返回0。
2. 递归逻辑：遍历所有可移动的相邻顶点（不能停在当前顶点），累加每个相邻顶点走remaining-1步回D的路径数。
3. 记忆化缓存：用Map存储已计算过的(顶点, 剩余步数)组合，避免重复计算。

代码实现 #

// 记忆化缓存，键格式为 "顶点-剩余步数"
const memo = new Map();

function countPaths(current, remaining) {
    const key = `${current}-${remaining}`;
    // 优先从缓存取结果
    if (memo.has(key)) {
        return memo.get(key);
    }

    // 剩余步数为0，判断是否在D点
    if (remaining === 0) {
        const result = current === 'd' ? 1 : 0;
        memo.set(key, result);
        return result;
    }

    // 剩余步数为1，非D点可直接回D，D点无法停留
    if (remaining === 1) {
        const result = current !== 'd' ? 1 : 0;
        memo.set(key, result);
        return result;
    }

    let total = 0;
    // 遍历所有可移动的相邻顶点
    for (const next of ['a', 'b', 'c', 'd']) {
        if (next !== current) {
            total += countPaths(next, remaining - 1);
        }
    }

    // 缓存当前状态的计算结果
    memo.set(key, total);
    return total;
}

// 测试用例
console.log(countPaths('d', 2));  // 输出3，符合预期
console.log(countPaths('d', 3));  // 输出6
console.log(countPaths('d', 15)); // 快速得到结果，无性能问题

优势说明 #

• 时间复杂度降至O(4*n)：只有4个顶点，每个顶点对应n种剩余步数，总共4n种状态，每种状态仅计算一次。
• 去掉了全局变量和路径数组，逻辑更简洁，无副作用。

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