Как определить таблицу памятки - PullRequest
Новая
       7

Как определить таблицу памятки

0 голосов
/ 02 ноября 2018

[Задал похожий вопрос ранее, но удалил предыдущую и изменил проблему]

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

Учитывая строку длины n, подпоследовательность - это любое непустое подмножество символов, читаемое слева направо. Например, если A = atc, то a, t, c, at, tc, ac, atc являются подпоследовательностями A. Учитывая две строки длины n, m, разработайте алгоритм, который выводит длину самой длинной общей подпоследовательности (LCS) двух строк.

Я придумал следующий метод: 

int lcs( char[] X, char[] Y, int m, int n ) 
  { 
    int L[][] = new int[m+1][n+1]; 

    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
    for (int i=0; i<=m; i++) 
    { 
      for (int j=0; j<=n; j++) 
      { 
        if (i == 0 || j == 0) 
            L[i][j] = 0; 
        else if (X[i-1] == Y[j-1]) 
            L[i][j] = L[i-1][j-1] + 1; 
        else
            L[i][j] = max(L[i-1][j], L[i][j-1]); 
      } 
    } 
  return L[m][n]; 
  }

Следующие три шага, на которых я немного размыт.

Насколько я понимаю, таблицу памятки можно определить как: 

memo[i][j] = length of longest substring

Лучший случай был бы, если 

memo[i][j] = 1

И рекурсивный шаг будет 

if (i == 0 || j == 0) 
    L[i][j] = 0; 
else if (X[i-1] == Y[j-1]) 
    L[i][j] = L[i-1][j-1] + 1; 
 else
     L[i][j] = max(L[i-1][j], L[i][j-1]);

Это правильный путь для понимания того, как работает запоминание?

...