C++迭代实现最长公共子序列报错误码-1073741819(0xC0000005)

实现最长公共子序列（Longest Common Subsequence，LCS）动态规划解法时，程序运行持续返回错误码-1073741819 (0xC0000005)，该错误码对应Windows平台内存访问违例（越界访问非法内存）。手动推演逻辑未发现明显问题，原始实现代码如下：

/* Dynamic Programming Solution */


#include <iostream>
#include <string>
#include <vector>
using namespace std ;

void input();
void lcs(string s1,string s2,unsigned int m ,unsigned int n);

void input(){
    string s1 , s2 ;
    unsigned int m , n ;
    cin >> s1 ;
    cout << flush ;
    cin >> s2 ;
    cout << flush ;
    m = s1.length();
    n = s2.length();
    lcs(s1,s2,m,n);
    // to main
}

// Tabulated function

void lcs(string s1,string s2,unsigned int m ,unsigned int n){
    vector <vector<int>> memo(m + 1);
    vector <int> v(n + 1);
    for(int i = 0 ; i <= m ; i++ ){
        memo.push_back(v);
    }
    for(int i = 0 ; i <= n ; i++ ){
        memo[0].push_back(0) ;
    }
    for(int i = 0 ; i < m ; i++ ) {
        memo[i].push_back(0);
    }
    for(int i = 1 ; i <= m ; i++ ){
        for(int j = 1 ; j <= n ; j++ ){
            if(s1[i - 1] == s2[j - 1]){
                memo[i][j] = 1 + memo[i - 1][j - 1];
            }else{
                memo[i][j] = max(memo[i - 1][j],memo[i][j - 1]);
            }
        }
    }
    cout << memo[m][n];
}

int main(){
    input();
    return 0 ;
}

核心问题出在DP数组memo的初始化逻辑：

• 代码第一行vector<vector<int>> memo(m + 1);已经创建了包含m+1个空vector<int>的二维数组，后续循环for(int i = 0 ; i <= m ; i++ ){ memo.push_back(v); }会额外往数组尾部追加m+1个长度为n+1的vector，最终memo总长度为2*(m+1)，但前m+1个位置的vector始终是空的。
• 后续两次push_back操作仅在空vector尾部追加了少量0值，没有把每个子vector初始化为长度n+1的定长数组。
• 双重循环计算DP值时，代码访问的是前m+1个空vector的j索引位置，属于典型的数组越界访问，直接触发内存访问违例报错。

直接修正二维DP数组的初始化逻辑，一次性创建m+1行、n+1列、初始值全为0的二维数组即可，替换原有错误的初始化代码。修复后的lcs函数实现如下：

void lcs(string s1,string s2,unsigned int m ,unsigned int n){
    // 直接初始化(m+1)行(n+1)列、全0的二维数组
    vector<vector<int>> memo(m + 1, vector<int>(n + 1, 0));
    
    for(int i = 1 ; i <= m ; i++ ){
        for(int j = 1 ; j <= n ; j++ ){
            if(s1[i - 1] == s2[j - 1]){
                memo[i][j] = 1 + memo[i - 1][j - 1];
            }else{
                memo[i][j] = max(memo[i - 1][j],memo[i][j - 1]);
            }
        }
    }
    cout << memo[m][n];
}

优化提示：可以把lcs函数的字符串参数改为const string&类型传引用，避免字符串拷贝带来的额外性能开销。

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