最长递增子序列问题：自顶向下DP代码为何无法正常运行？

给定整数数组 nums，返回最长严格递增子序列的长度。
子序列是可通过删除数组中部分或零个元素、不改变剩余元素原有顺序推导得到的序列，例如 [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列为 [2,3,7,101]，因此长度为4。

编写的纯递归代码可以正确得到运行结果，但自顶向下（TopDown）动态规划版本无法正常工作。代码仅新增了dp向量存储计算结果做记忆化复用，未修改其他递归逻辑，无法定位问题。

可正常运行的递归代码 #

int lengthOfLIS(vector<int>& arr, int i=0, int prev= INT_MIN){
        //........... base case............
        if(i==arr.size()) return 0;
        //........... recursive case...........
        // take if it is grater than prev
        int X = INT_MIN;
        if(arr[i] > prev)
            X = 1 + lengthOfLIS(arr, i+1, arr[i]);
        // ignore
        int Y = lengthOfLIS(arr, i+1, prev);
    
        return max(X, Y);
    }

运行异常的自顶向下DP代码 #

int sol(vector<int> arr, vector<int>& dp, int i=0, int prev= INT_MIN){
        //........... base case............
        if(i==arr.size()) return dp[i]=0;
        if(dp[i]!=-1) return dp[i];
        //........... recursive case...........
        // take if it is grater than prev
        int X = INT_MIN;
        if(arr[i] > prev)
            X = 1 + sol(arr, dp, i+1, arr[i]);
        // ignore
        int Y = sol(arr, dp, i+1, prev);
    
        return dp[i] = max(X, Y);
    }

代码存在两个核心问题：

• 记忆化状态维度缺失：递归函数的返回值由当前遍历位置i、上一个选中的元素值prev两个独立参数共同决定，但你仅用一维数组dp[i]存储结果，默认同一位置i在任意prev取值下计算结果一致，和实际逻辑完全不符。第一次递归到i位置时，存储的是对应某一个prev值的计算结果，后续其他prev场景下走到i位置会直接读取这个错误的缓存值，必然得到错误结果。
• 边界与传参错误：一是arr采用值传递，每次递归调用都会完整拷贝整个数组，时间和内存开销会随递归深度指数级上升；二是当i等于数组长度时访问dp[i]，若dp数组长度和输入数组等长，这里会触发数组越界，属于未定义行为。

可以调整DP状态定义，用dp[i]表示以第i个元素为子序列结尾时的最长递增子序列长度，这种定义下不需要记录prev参数，不会出现记忆化冲突的问题，修正后的参考代码如下：

// 计算以i位置元素为结尾的最长递增子序列长度
int sol(vector<int>& arr, vector<int>& dp, int i){
    if(dp[i] != -1) return dp[i];
    int maxLen = 1; // 仅选取当前元素时，长度为1
    for(int j = 0; j < i; j++){
        if(arr[j] < arr[i]){
            maxLen = max(maxLen, 1 + sol(arr, dp, j));
        }
    }
    return dp[i] = maxLen;
}

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, -1);
    int res = 0;
    // 遍历所有位置作为子序列结尾，取最大值
    for(int i = 0; i < n; i++){
        res = max(res, sol(nums, dp, i));
    }
    return res;
}

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