При инициализации 2D - массива первая строка инициализируется мусором

Question

Решаю задачу нахождения LSC "Наибольшей общей последовательности". Мне необходимо построить двумерный массив [длина строки 1] [длина строки 2] и заполнить его нулями. при попытке так сделать первая строка массива заполняется мусором. предполагаю, что это связано с тем, что длина строки не является constexpr, но подтверждений этому найти не смог.

int main() {
    string a = "asdfga";
    string b = "qwerty";
    auto x = a.size() + 1;
    auto y = b.size() + 1;
  
    int arr[x][y] = {0};
    for (auto i = 0; i < x; ++i) {
        for(auto j = 0; j < y; ++j) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

По совету HolyBlackCat попробовал реализовать с одним вектором. Вроде работает, но пока не понял почему вектор составляется по столбцам, а не построчно

string a; //"baccbca"
string b; //"abcabaac"
cin >> a >> b; 
size_t x = a.size() + 1;
size_t y = b.size() + 1;
cout << x + 1 << " " << y + 1 << endl;

vector<int> arr((x)*(y), 0);
for (int i = 1; i < x; ++i) {
    for (int j = 1; j < y; ++j) {
        if (a[i - 1] == b[j - 1])
            arr[j + i * y] = arr[(j + i * y) - y - 1] + 1;
        else
            arr[j + i * y] = max(arr[(j + i * y) - y], arr[(j + i * y) - 1]);
    }
}
cout << arr[x*y - 1];

Answer 1

В общем задача наибольшей общей подпоследовательности решается с помощью ДП, строим двумерный вектор

vector <vector <int>> dp;
int n = a.size();
int m = b.size();
dp.resize(max(n,m));
for (size_t i = 0; i < max(n,m); ++i) dp[i].assign(min(m,n),0);

Дальше мы работаем через рекурсивную формулу: lcs(i,j) ==

lcs(i-1,j-1)+1 {x[i]==y[i]}
lcs(max(lcs(i-1,j),lcs(i,j-1)) else

БЛОГ НА HUSL

При инициализации 2D - массива первая строка инициализируется мусором

Ответы (1 шт):