LeetCode 300：最长递增子序列一维DP记忆化递归问题求助

问题背景 #

针对最长递增子序列问题，我有一段无记忆化的递归代码，能正常运行但因未做记忆化导致超时：

class Solution {
    public static int recurse(int prev, int curr, int[] nums) {
        if(curr == nums.length) return 0;

        int elect = 0;
        int ignore = 0;
        if(prev == -1 || nums[prev] < nums[curr]) {
            elect = 1 + recurse(curr, curr + 1, nums);
        }
        ignore = recurse(prev, curr + 1, nums);
        return Math.max(elect, ignore);
    }
    public int lengthOfLIS(int[] nums) {
        return recurse(-1, 0, nums);
    }
}

lengthOfLIS函数通过调用recurse(-1, 0, nums)启动递归。

我尝试用一维数组存储子问题缓存结果来实现记忆化，但多次尝试都得到错误结果，以下是我的错误代码（未展示dp数组初始化代码）：

public static int recurse3(int prev, int curr, int nums[]) {
    if(curr == nums.length) return 0;
    if(dp2[curr] != -1) return dp2[curr];
    int op1 = 0;
    if(prev == -1 || nums[curr] > nums[prev]) {
        op1 = 1 + recurse3(curr, curr + 1, nums);
    }
    int op2 = recurse3(prev, curr + 1, nums);
    dp2[curr] = Math.max(op1, op2);
    return Math.max(op1, op2);
}

请问如何正确使用一维dp数组实现该递归的记忆化？

问题分析 #

你的错误核心在于：一维dp2[curr]仅记录了当前curr位置的最大结果，但忽略了prev这个关键状态——不同的prev对应curr位置的最优解完全不同。比如当prev指向不同索引时，nums[prev]的数值差异会决定是否能选取curr位置的元素，最终得到的子序列长度自然不同，一维数组无法覆盖这种多状态的情况。

不过我们可以通过重新定义递归状态，用一维DP数组实现记忆化，无需依赖二维数组。

正确的一维DP记忆化实现 #

我们重新定义递归函数的含义：dp[i]表示以nums[i]结尾的最长递增子序列的长度。基于这个定义，改写后的递归逻辑如下：

class Solution {
    private int[] dp;
    private int[] nums;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        dp = new int[nums.length];
        // 初始化dp数组为-1，表示该子问题未计算
        for (int i = 0; i < nums.length; i++) {
            dp[i] = -1;
        }

        int maxLen = 0;
        // 遍历每个位置作为子序列的结尾，取所有结果中的最大值
        for (int i = 0; i < nums.length; i++) {
            maxLen = Math.max(maxLen, recurse(i));
        }
        return maxLen;
    }

    // 递归函数：返回以nums[index]结尾的最长递增子序列长度
    private int recurse(int index) {
        // 已计算过直接返回缓存值
        if (dp[index] != -1) {
            return dp[index];
        }

        // 至少包含自身，长度为1
        int maxVal = 1;
        // 遍历index之前的所有元素，找到能接在前面的最长子序列
        for (int i = 0; i < index; i++) {
            if (nums[i] < nums[index]) {
                maxVal = Math.max(maxVal, 1 + recurse(i));
            }
        }
        // 缓存当前子问题的结果
        dp[index] = maxVal;
        return maxVal;
    }
}

为什么这个方案可行？ #

1. 状态定义清晰唯一：dp[index]仅依赖于前面所有比nums[index]小的元素的dp[i]，每个状态独立且唯一，不会像原代码那样受prev的多重状态干扰。
2. 记忆化有效覆盖子问题：每个dp[index]只会计算一次，后续递归直接读取缓存值，时间复杂度从原递归的O(2^n)降至O(n²)，彻底解决超时问题。
3. 符合一维DP的需求：通过转换问题视角，把原二维状态的递归转化为一维状态的子问题，完美适配你想用一维数组实现记忆化的需求。

如果坚持要保留原递归的prev和curr参数，那必须使用二维DP数组（可以把prev偏移1位，用dp[prev+1][curr]存储状态），但上述一维DP的实现方式更简洁高效，也更易理解。

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