LCS에 대한 2 차원 배열 테이블

Question

필자는 Longest Common Subsequence 문제를 해결하기위한 코드를 작성했습니다. 정의 할 m x w 차원의 2D 테이블이 필요합니다. 전역 변수로 정의했지만 용량 초과 오류가 발생했습니다.

#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]); 
} 

나는 벡터의 벡터를 사용하고 있지만 동시에 크기를 mxw로 정의 할 수 있습니까? 정규

은 벡터를 미리 정의하고 코드에서와 같이 첨자 연산자를 사용하여 액세스하려는 것으로 충분하지 않습니다. 사용

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

Answer 1

예, 당신이 한 모든 내부 벡터가 같은 크기에 있어야 할 수있다.

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

첫 번째 인자 인 count (많은 개체 처음 vector이어야 방법)과 두 번째 인수는 그 각각을 초기화하는 데 사용되는 값이다. 위의 경우에 9000 배의 숫자로 채워지는 9000 개의 벡터로 끝납니다.

의 전체 목록은 다음과 같습니다.

Answer 2

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

Answer 3

크기 m x w의 "벡터의 벡터"를 만들 수 있습니다.

이 때문에 두 변수 STD : 벡터 생성자 작품 : 첫번째 파라미터 번째 매개 변수 값 val으로 크기 n 소요

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

때문에 vector<int>(w)의 m 사본있다, 크기가 w 인 vector<int> (기본값은 int()이며 0 임)의 m 복사본입니다.

참조 :

• std::vector