Самое длинное повторение общей подпоследовательности

Повторение для lcs:

L[i,j] = max(L[i-1,j], L[i,j-1]) if a[i] != a[j]

Можете ли вы сказать мне, почему это i-1 или j-1? Почему L[i,j] = L[i-1,j-1] неправильно?


dynamic lcs
person Faiz Halde    schedule 17.04.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы рассматриваете случай, когда a[i] != a[j] означает, что буквы, которые вы сейчас сравниваете в двух последовательностях A и B, различны. Следовательно, длина самой длинной общей подпоследовательности зависит от двух вещей:

  1. самая длинная общая подпоследовательность текущей подстроки A минус ее первый символ и B, т.е. L[i-1,j] ;
  2. самая длинная общая подпоследовательность A и текущая подстрока B за вычетом ее первого символа, т. е. L[i,j-1].

Если бы L[i-1,j-1] было правильным, это означало бы, что текущие символы как в A, так и в B не учитываются, у них нет «шанса» быть частью подпоследовательности.

См., например, это объяснение (обратите внимание, что оно работает вперед в последовательностях вместо обратного).

person Zoyd    schedule 17.04.2014
comment
Потрясающий. Прямой подход подводит итог. - person Faiz Halde; 17.04.2014