最长递增子序列(LIS)递归实现正确 同逻辑DP版本输出错误求助

你的DP代码错误的核心是状态定义不完整：

• 原递归函数的结果由两个参数共同决定：currIndex（当前遍历到的下标）、maxVal（当前已选子序列的最后一个元素值）
• 但你定义的DP数组仅用currIndex作为唯一索引，相当于默认同一个下标对应的返回值是固定的，忽略了不同maxVal会带来不同结果的情况，导致缓存了错误的结果。

以你给出的测试用例举例：
当第一次遍历到下标1（元素为3）时，此时传入的maxVal是第一个元素6，3<6无法选中，最终计算得到当前分支下dp[1] = 3并缓存；后续当逻辑走到放弃第一个元素6、maxVal为-1的分支时，再次遇到下标1，本应计算出3>=-1可以选中、最终结果为4，但代码直接返回了之前缓存的3，导致最终结果错误。

这里给出两种可选的修复方式：

方案1：扩展DP状态为二维 #

将DP数组调整为二维，同时记录currIndex和maxVal对应的结果，为了节省空间可以对数组元素做坐标压缩：

// 坐标压缩处理所有可能的maxVal，把值映射为下标
// dp[i][j]表示当前处理到第i个元素，上一个选中的元素是压缩后的第j个值时的最长LIS长度
int LISdp(int arr[], int n, int currIndex, int maxValIdx, vector<vector<int>> &dp, vector<int>& sortedArr) {
    if (currIndex == n) return 0;
    if (dp[currIndex][maxValIdx + 1] != -1) return dp[currIndex][maxValIdx + 1]; // maxVal=-1对应索引0
    int included = 0, notIncluded = 0;
    int maxVal = maxValIdx == -1 ? -1 : sortedArr[maxValIdx];
    if (arr[currIndex] > maxVal) {
        int currValIdx = lower_bound(sortedArr.begin(), sortedArr.end(), arr[currIndex]) - sortedArr.begin();
        included = 1 + LISdp(arr, n, currIndex + 1, currValIdx, dp, sortedArr);
    }
    notIncluded = LISdp(arr, n, currIndex + 1, maxValIdx, dp, sortedArr);
    return dp[currIndex][maxValIdx + 1] = max(included, notIncluded);
}

// 主函数中调用前先做坐标压缩
int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 坐标压缩
    vector<int> sortedArr(arr, arr+n);
    sort(sortedArr.begin(), sortedArr.end());
    sortedArr.erase(unique(sortedArr.begin(), sortedArr.end()), sortedArr.end());
    vector<vector<int>> dp(n, vector<int>(sortedArr.size() + 1, -1));
    cout << LISdp(arr, n, 0, -1, dp, sortedArr);
    return 0;
}

方案2：改用迭代DP实现（更常用，空间更优） #

使用常规的LIS DP定义：dp[i]表示以第i个元素结尾的最长递增子序列长度，最终取整个dp数组的最大值即可：

int LISdp(int arr[], int n) {
    vector<int> dp(n, 1);
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

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