使用vector时修改函数返回类型后无输出的技术咨询

Let's break down the problems in your code and fix them so you can get the expected LCS sequence output:

1. Critical Indexing Bug in DP Table Calculation #

Looking at your code snippet, there's a glaring mistake in the equality check that's breaking your DP table calculation:

else if (a[i - 1] == b[i - 1])  // Wrong!

You're using the outer loop variable i to index into b, but you should be using the inner loop variable j here. This causes incorrect element comparisons (and potentially out-of-bounds access if i > b.size()), which completely invalidates your DP table. The correct line should be:

else if (a[i - 1] == b[j - 1])

2. Missing Backtracking Logic for LCS Sequence #

You mentioned changing the function's return type to vector<int> (from what was likely an integer representing the LCS length). But your current code only builds the DP table L—it doesn't actually generate the LCS sequence from that table. Without this step, the function will return an empty or uninitialized vector, which explains why you see no output.

Here's the complete fixed function with backtracking included:

#include <vector>
#include <algorithm>

using namespace std;

vector<int> lcs2(vector<int> &a, vector<int> &b) {
    // Initialize DP table with (a.size()+1) rows and (b.size()+1) columns
    vector<vector<int>> L(a.size() + 1, vector<int>(b.size() + 1, 0));

    // Fill the DP table (loop logic is correct once we fix the indexing bug)
    for (int i = 0; i <= a.size(); ++i) {
        for (int j = 0; j <= b.size(); ++j) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            } else if (a[i - 1] == b[j - 1]) {
                L[i][j] = L[i-1][j-1] + 1;
            } else {
                L[i][j] = max(L[i-1][j], L[i][j-1]);
            }
        }
    }

    // Backtrack from L[a.size()][b.size()] to build the LCS sequence
    vector<int> lcs;
    int i = a.size();
    int j = b.size();

    while (i > 0 && j > 0) {
        if (a[i-1] == b[j-1]) {
            // Add matching element to LCS (we'll reverse it later for correct order)
            lcs.push_back(a[i-1]);
            i--;
            j--;
        } else if (L[i-1][j] > L[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    // Reverse to get the proper forward order
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

3. How to Verify the Output #

To see the result, call the function and print the returned vector, like this:

#include <iostream>

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    vector<int> b = {3, 4, 5, 6, 7};
    vector<int> result = lcs2(a, b);

    cout << "LCS sequence: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    // Expected output: 3 4 5
    return 0;
}

Key Notes to Remember #

• Your use of <= in the loops is correct—since the DP table has dimensions [a.size()+1][b.size()+1], indices run from 0 to a.size() and 0 to b.size().
• Mixing up loop variables (i vs j) is a common mistake, but it's crucial to double-check when accessing arrays or vectors.
• When returning a sequence instead of just length, backtracking is mandatory to reconstruct the actual LCS from the DP table.

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