Кто изменил мою матрицу? Таинственная ошибка

Question

Я застрял в этой маленькой ошибке последние два часа, и теперь я в отчаянии. Любая помощь высоко ценится!

Алгоритм для создания матрицы для задачи Longest Common Subsequence между двумя последовательностями. И матрица используется в качестве справочной таблицы в подходе Dynamic Programming. Приклеивание соответствующего кода

#include <vector> 
#include <cstdio> 
#include <math.h> 

using namespace std; 
int main() 
{ 
    vector<int> A, B; 
    A.push_back(0); 
    A.push_back(15); 
    A.push_back(20); 
    B.push_back(0); 
    B.push_back(20); 
    B.push_back(15); 

    int a = 2; 
    int b = 2; 
    int matrix[a][b]; 
    memset(matrix, 0, sizeof(int)*a*b); 

    for (int i = 0; i <= a; ++i) 
    { 
    for (int j = 0; j <= b; ++j) 
    { 
     if (i == 0 || j == 0) 
     { 
     matrix[i][j] = 0; 
     } else 
     { 
     if (A[i] == B[j]) 
     { 
      matrix[i][j] = matrix[i - 1][j - 1] + 1; 
      printf("matrix at row %i column %i: %i\n", i, j, matrix[i][j]); 
     } else 
     { 
      matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1]); 
     } 
     } 
    } 
    } 
    printf("matrix at row 1 column 2: %i\n", matrix[1][2]); 
    printf("matrix at row 2 column 1: %i\n", matrix[2][1]); 
} 

Если я скомпилировать и запустить его с

g++ -Wall soquestion1.cpp -o soquestion1 
./soquestion1 

Я получаю

matrix at row 1 column 2: 1 
matrix at row 2 column 1: 1 
matrix at row 1 column 2: 0  #WTHHHHHH, who changed my matrix!? 
matrix at row 2 column 1: 1 

Спасибо за чтение, что далеко.

Answer 1

for (int i = 0; i <= a; ++i) 
    { 
    for (int j = 0; j <= b; ++j) 
    { 

Это ваша проблема. Вы выходите за пределы, в результате чего ... «что-то».

Сделайте это <a и <b, и все должно быть в порядке. Также вы получаете доступ к самой матрице, на самом деле не читали, что там делает. Вы проверили, какой результат ДОЛЖЕН быть?

printf("matrix at row 1 column 2: %i\n", matrix[1][2]); 
    printf("matrix at row 2 column 1: %i\n", matrix[2][1]); 

Это должно быть matrix[0][1] и matrix[1][0]

Примечание: ожидаемый результат должен быть 0 и 0

Answer 2

Ваш код рода беспорядок. Я очистил его.

#include <algorithm> 
#include <cstdio> 

int main() 
{ 
    int A[] = { 0, 15, 20 }; 
    int B[] = { 0, 20, 15 }; 

    const size_t MatrixDim = 3; 
    int matrix[MatrixDim][MatrixDim] = { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } }; 
    // or memset(matrix, 0, sizeof(matrix)); 

    // only operate on dimensions 1 and 2, leave 0,j and i,0 elements as 0. 
    for (size_t i = 1; i < MatrixDim; ++i) 
    { 
    for (size_t j = 1; j < MatrixDim; ++j) 
    { 
     if (A[i] == B[j]) 
     { 
     matrix[i][j] = matrix[i - 1][j - 1] + 1; 
     printf("a. matrix at row %i column %i: %i\n", i, j, matrix[i][j]); 
     } 
     else 
     { 
     matrix[i][j] = std::max(matrix[i - 1][j], matrix[i][j - 1]); 
     printf("b. matrix at row %i column %i: %i\n", i, j, matrix[i][j]); 
     } 
    } 
    } 

    for (size_t i = 0; i < MatrixDim; ++i) { 
    for (size_t j = 0; j < MatrixDim; ++j) { 
     printf("%02d ", matrix[i][j]); 
    } 
    printf("\n"); 
    } 
} 

Живая демонстрация: http://ideone.com/vGk4oB

Выход:

a. matrix at row 1 column 2: 1 
a. matrix at row 2 column 1: 1 
b. matrix at row 2 column 2: 1 
00 00 00 
00 00 01 
00 01 01