Поиск наибольшей общей подпоследовательности(LCS) с помощью динамического программирования

[Все алгоритмы нахождения LCS]

Очень простой и понятный алгоритм, основанный на двумерном ДП.
Сложность по памяти и времени O(n*m).

Рассмотрим две строчки: A = “bedcadb” и B = “abcdede”. 
1) Буквы строчки A напишем перед строками матрицы, а элементы строчки B над столбцами матрицы.
2) Матрица будет иметь нулевые столбец и строку, состоящие из нулей.
3) Саму матрицу давайте назовем L.
4) В элементе матрицы L[i][j] будет хранится длина наибольшей общей подпоследовательности для префиксов A[1..i] и B[1..j].

Из п.4 делаем вывод, что нумерация букв в строках с единицы.
Префикс A[1..i] – это первые i символов строки A.

Для начала давайте заполним матрицу L по этим 4 принципам:

Разберем элемент L[3][4]. В данном случае рассматриваются два префикса: “bed” и “abcd”. Чисто интуитивно можно догадаться, что lcs для этих двух строк будет “bd”, поэтому в самом элементе храним 2. Все остальные элементы можно заполнить интуитивно.

Вот как раз на этом моменте выключаем интуицию(в рамках разумного) и начинаем искать “научный” принцип заполнения этой матрицы.

В ходе Ваших рассуждений должны появится следующие рекуррентные формулы:
             
           | L[i-1][j-1] + 1, если a[i] == b[j]
L[i][j] = < 
           | max(L[i-1][j],L[i][j-1]), иначе
Результирующая длина lcs для полных строк a и b находится в элементе L[7][7].

Теперь давайте научимся восстанавливать lcs по данной матрице. Эту задачу я поручаю на самостоятельное изучение. Если все таки эта задача вызовет затруднения, оставляю в качестве подсказки этот рисунок.

Оранжевая lcs: bed
Желтая    lcs: bcd
Затем тренируемся на задачах:
1) Найти длину LCS
2) По матрице восстановить саму LCS
Демонстрационное решение: здесь