如何为整数数组最长递增子序列的迭代计算添加记忆化？

我正在解决最长递增子序列问题，理论上明白要为每个索引分配对应的子序列长度，但用迭代方法编码时遇到了困难。当前我的JavaScript代码如下，想请教如何为这个迭代解法添加记忆化优化：

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
    let maxSubsequenceLength = -Infinity;
    const stack = [[-1, 0, 0]];
    const cache = new Map();

    while (stack.length > 0) {
        const [previousIndex, currentIndex, currentLength] = stack.pop();

        if (currentIndex === nums.length) {
            maxSubsequenceLength = Math.max(maxSubsequenceLength, currentLength);
        } else {
            const previousNumber = nums[previousIndex] ?? -Infinity;
            const currentNumber = nums[currentIndex];

            if (currentNumber > previousNumber) {
                stack.push([currentIndex, currentIndex + 1, currentLength + 1]);
            }

            stack.push([previousIndex, currentIndex + 1, currentLength]);
        }
    }

    return maxSubsequenceLength;
};

问题分析 #

你当前的代码是用栈模拟递归的暴力搜索，每个状态由previousIndex（上一个选中元素的索引）和currentIndex（当前遍历到的索引）决定，但暴力解法会重复计算大量相同状态，导致时间复杂度很高。记忆化的核心就是把这些状态的计算结果缓存起来，避免重复运算。

优化思路 #

1. 缓存键设计：用${previousIndex},${currentIndex}作为缓存的key，这两个值唯一确定当前的搜索状态。
2. 栈状态标记：给栈中的元素增加一个isProcessed标记，区分首次弹出（需要先处理子问题）和二次弹出（子问题已解决，可计算当前状态结果）。
3. 子问题依赖处理：先处理当前状态的两个子问题（不选当前元素、选当前元素（如果符合条件）），等子问题的结果存入缓存后，再计算当前状态的最长长度并缓存。

优化后的代码 #

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
    const cache = new Map();
    // 栈元素格式：[上一个选中元素索引, 当前遍历索引, 是否已处理子问题]
    const stack = [[-1, 0, false]];
    let maxLength = 0;

    while (stack.length > 0) {
        const [prevIdx, currIdx, isProcessed] = stack.pop();

        // 终止条件：遍历完所有元素，该状态的最长长度为0
        if (currIdx === nums.length) {
            const key = `${prevIdx},${currIdx}`;
            cache.set(key, 0);
            maxLength = Math.max(maxLength, 0);
            continue;
        }

        const key = `${prevIdx},${currIdx}`;
        // 二次弹出，子问题已处理，计算当前状态结果
        if (isProcessed) {
            const prevNum = prevIdx === -1 ? -Infinity : nums[prevIdx];
            const currNum = nums[currIdx];
            
            // 不选当前元素的最长长度：取子问题[prevIdx, currIdx+1]的结果
            const notTake = cache.get(`${prevIdx},${currIdx+1}`);
            // 选当前元素的最长长度：符合递增条件则取1+子问题[currIdx, currIdx+1]的结果，否则为0
            const take = currNum > prevNum ? 1 + cache.get(`${currIdx},${currIdx+1}`) : 0;
            
            // 当前状态的最长长度是两种选择的最大值
            const currentMax = Math.max(notTake, take);
            cache.set(key, currentMax);
            maxLength = Math.max(maxLength, currentMax);
            continue;
        }

        // 首次弹出，先标记为待处理压回栈，再压入子问题状态
        stack.push([prevIdx, currIdx, true]);
        // 先压入不选当前元素的子问题（栈后进先出，确保先处理子问题）
        stack.push([prevIdx, currIdx + 1, false]);

        // 若当前元素符合递增条件，压入选当前元素的子问题
        const prevNum = prevIdx === -1 ? -Infinity : nums[prevIdx];
        if (nums[currIdx] > prevNum) {
            stack.push([currIdx, currIdx + 1, false]);
        }
    }

    return maxLength;
};

优化效果 #

通过记忆化缓存，每个状态只会被计算一次，时间复杂度从暴力解法的O(2^n)降到了O(n²)，和动态规划解法的时间复杂度一致，同时保留了迭代实现的方式。

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