LCS的二维数组表格

Question

我已经写了代码来解决最长的公共子序列problem.Just需要定义的m×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]);
}

我正在考虑使用向量的向量，但是否可以同时将大小定义为m x w？一个正常的

vector < vector <int> > lcs

这是不够的，因为我想要预定义向量并使用代码中的下标操作符访问它。

Answer 1

可以，只要所有内部向量的大小相同即可。

std::vector< std::vector<int> > v(9000, std::vector<int>(9000, 23));

第一个参数是count (vector中最初应该有多少个对象)，第二个参数是用于初始化每个对象的值。在上面的例子中，你最终得到了9000个向量，每个向量都填充了数字23的9000倍。

is here的vector构造函数的完整列表。

Answer 2

使用

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

创建一个大小为m x w的“向量的向量”。

这要归功于两个参数std::vector构造函数：

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

它将大小n作为其第一个参数，并将值val作为其第二个参数，因此存在vector<int>(w)的m副本，即大小为w的m副本(其默认值为int()，为0)。

参考文献

• std::vector

Answer 3

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