c++ - LCS 的二维数组表

Question

我已经编写了解决最长公共(public)子序列问题的代码。只需要定义 m X w 维度的二维表。我已将其定义为全局变量，但它引发了超出容量的错误。

#define FOR(i,n) for( i = 0; i < n ; ++ i)
int LCS(const char M[],int m, const char W[], int w)
{
    // m length of M w length of W
    int ans,min,i,j;
    // lcs table needs to be defined with required dimensions 
    min = ( m >= w ) ? w : m;

    FOR(i,m)
        FOR(j,w)
        {
            if (i == 0 || j == 0)
                lcs[i][j] = 0; // repetitive
            else if (M[i] == W[j] )
                lcs[i][j] = lcs[i-1][j-1] + 1;
            else
                lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1]);
        }

        return (min == lcs[m-1][w-1]);
}

我正在考虑使用 vector of vector 但是否可以同时将大小定义为 m x w？一个普通的

vector < vector <int> > lcs

这还不够，因为我想预先定义 vector 并使用代码中的下标运算符访问它。

Answer 1

使用

vector<vector<int>> lcs(m, vector<int>(w));

创建一个大小为 m x w 的“vector 的 vector ” .

这是因为有两个参数 std::vector 构造函数:

vector(size_type n, const value_type& val = value_type());

其大小为 n作为它的第一个参数和值 val作为它的第二个参数，所以有 m拷贝vector<int>(w) , 即 m拷贝vector<int>尺寸w (默认值为 int() ，即 0)。

引用:

• std::vector