如何优化JavaScript递归代码 解决选左右卡牌求最高总和问题

你当前的朴素递归解法时间复杂度为O(2ⁿ)，n为卡牌总数，随着n增长计算量会指数级上升，核心问题是大量重复子问题被反复计算：例如不同递归路径可能多次进入同一个子区间[i,j]的计算逻辑，每次都重复执行后续递归，产生大量无用开销。

优化思路：动态规划消除重复计算 #

我们可以通过存储已计算的子区间结果，将时间复杂度降低到O(n²)，适配更大规模的输入。

状态定义 #

定义dp[i][j]为剩余卡牌为区间[i,j]时，可获得的最大总和。
这里可以通过区间长度推导当前的选取次数x：设总卡牌数为n，当前区间长度len = j - i + 1，则已选取的卡牌数为n - len，当前是第x = n - len次选取（从0开始计数），无需额外将x作为状态参数。

状态转移方程 #

每次可以选择拿左端或右端的卡牌，取收益更大的选项：

dp[i][j] = max( cards[i] * 2^x + dp[i+1][j], cards[j] * 2^x + dp[i][j-1] )
边界条件：当i == j时，只剩最后一张卡牌，dp[i][i] = cards[i] * 2^(n-1)

优化代码实现 #

版本1：记忆化递归（自顶向下） #

在原有递归逻辑基础上增加缓存存储已计算的区间结果：

function solve(cards) {
    const n = cards.length;
    // 预计算2的幂，避免重复调用Math.pow提升性能
    const pow2 = new Array(n).fill(1);
    for (let k = 1; k < n; k++) {
        pow2[k] = pow2[k - 1] * 2;
    }
    // 缓存数组，-1代表该区间未计算
    const memo = new Array(n).fill(0).map(() => new Array(n).fill(-1));

    function dfs(i, j) {
        if (i > j) return 0;
        // 已计算过的区间直接返回缓存结果
        if (memo[i][j] !== -1) return memo[i][j];
        const x = n - (j - i + 1);
        const takeLeft = cards[i] * pow2[x] + dfs(i + 1, j);
        const takeRight = cards[j] * pow2[x] + dfs(i, j - 1);
        memo[i][j] = Math.max(takeLeft, takeRight);
        return memo[i][j];
    }

    return dfs(0, n - 1);
}

版本2：迭代动态规划（自底向上） #

按区间长度从小到大计算，避免递归函数调用开销，性能更高：

function solve(cards) {
    const n = cards.length;
    const pow2 = new Array(n).fill(1);
    for (let k = 1; k < n; k++) {
        pow2[k] = pow2[k - 1] * 2;
    }
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));

    // 初始化长度为1的区间
    for (let i = 0; i < n; i++) {
        dp[i][i] = cards[i] * pow2[n - 1];
    }

    // 枚举区间长度从2到n
    for (let len = 2; len <= n; len++) {
        // 枚举左端点
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            const x = n - len;
            dp[i][j] = Math.max(
                cards[i] * pow2[x] + dp[i + 1][j],
                cards[j] * pow2[x] + dp[i][j - 1]
            );
        }
    }

    return dp[0][n - 1];
}

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