dynamic-programming
Подследующие алгоритмы
Поиск…
Самая длинная общая подпоследовательность
Одна из наиболее важных реализаций динамического программирования - поиск самой длинной общей подпоследовательности . Сначала определим некоторые основные термины.
подпоследовательности:
Подпоследовательность представляет собой последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка остальных элементов. Допустим, у нас есть строка ABC . Если мы стираем нуль или один или несколько символов из этой строки, мы получаем подпоследовательность этой строки. Таким образом, подпоследовательности строки ABC будут { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Даже если мы удалим все символы, пустая строка также будет подпоследовательностью. Чтобы узнать подпоследовательность, для каждого символа в строке мы имеем два варианта: либо мы берем символ, либо нет. Поэтому, если длина строки равна n , существует 2 n подпоследовательностей этой строки.
Самая длинная общая подпоследовательность:
Как следует из названия, из всех общих подпоследовательностей между двумя строками самая длинная общая подпоследовательность (LCS) - это та, которая имеет максимальную длину. Например: общие подпоследовательности между «HELLOM» и «HMLD» - это «H» , «HL» , «HM» и т. Д. Здесь «HLL» является самой длинной общей подпоследовательностью, длина которой 3.
Метод грубой силы:
Мы можем сгенерировать все подпоследовательности двух строк с использованием обратного отсчета . Затем мы можем сравнить их, чтобы выяснить общие подпоследовательности. После того, как нам понадобится узнать ту, которая имеет максимальную длину. Мы уже видели, что существует 2 n подпоследовательностей строки длины n . Потребуются годы, чтобы решить проблему, если наши русские кресты 20-25 .
Метод динамического программирования:
Давайте подходим к нашему методу с примером. Предположим, что мы имеем две строки abcdaf и acbcf . Обозначим их с s1 и s2 . Таким образом, самая длинная общая подпоследовательность этих двух строк будет «abcf» , которая имеет длину 4. Снова напоминаю вам, подпоследовательности не обязательно должны быть непрерывными в строке. Чтобы построить «abcf» , мы игнорировали «da» в s1 и «c» в s2 . Как это узнать, используя динамическое программирование?
Мы начнем с таблицы (2D-массив), содержащей все символы s1 в строке и все символы s2 в столбце. Здесь таблица 0-индексируется, и мы помещаем символы от 1 до и далее. Мы будем перемещать таблицу слева направо для каждой строки. Наша таблица будет выглядеть так:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Здесь каждая строка и столбец представляют длину самой длинной общей подпоследовательности между двумя строками, если мы берем символы этой строки и столбца и добавляем к префиксу перед ним. Например: Таблица [2] [3] представляет длину самой длинной общей подпоследовательности между «ac» и «abc» .
0-й столбец представляет собой пустую подпоследовательность s1 . Точно так же 0-я строка представляет собой пустую подпоследовательность s2 . Если взять пустую подпоследовательность строки и попытаться сопоставить ее с другой строкой, независимо от того, как долго длина второй подстроки, то общая подпоследовательность будет иметь длину 0. Таким образом, мы можем заполнить 0-й ряд и 0-й столбцы нулями. Мы получаем:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Давай начнем. Когда мы заполняем таблицу [1] [1] , мы спрашиваем себя, если бы у нас была строка a и другая строка a и ничего больше, какая будет самая длинная общая подпоследовательность здесь? Длина LCS здесь будет 1. Теперь рассмотрим таблицу [1] [2] . У нас есть строка ab и строка a . Длина LCS будет равна 1. Как вы можете видеть, остальные значения будут также 1 для первой строки, так как он рассматривает только строку a с abcd , abcda , abcdaf . Итак, наша таблица будет выглядеть так:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Для строки 2, которая теперь будет включать c . Для таблицы [2] [1] мы имеем ac с одной стороны, а с другой стороны. Таким образом, длина LCS равна 1. Откуда у нас это 1? С вершины, обозначающей LCS a между двумя подстроками. Итак, мы говорим, что если s1 [2] и s2 [1] не совпадают, то длина LCS будет максимальной длины LCS сверху или слева . Взяв длину LCS сверху, это означает, что мы не берем текущий символ из s2 . Аналогично, взяв длину LCS слева, мы не берем текущий символ из s1 для создания LCS. Мы получаем:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Итак, наша первая формула будет:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Двигаясь дальше, для таблицы [2] [2] имеем строку ab и ac . Поскольку c и b не являются одинаковыми, мы помещаем максимум сверху или слева здесь. В этом случае это снова 1. После этого для таблицы [2] [3] имеем строку abc и ac . На этот раз текущие значения обеих строк и столбцов совпадают. Теперь длина LCS будет равна максимальной длине LCS до + 1. Как мы получаем максимальную длину LCS до сих пор? Мы проверяем диагональное значение, которое представляет наилучшее совпадение между ab и a . Из этого состояния для текущих значений мы добавили еще один символ к s1 и s2, который оказался одним и тем же. Таким образом, длина LCS, разумеется, возрастет. Мы поместим 1 + 1 = 2 в таблицу [2] [3] . Мы получаем,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Итак, наша вторая формула будет:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Мы определили оба случая. Используя эти две формулы, мы можем заполнить всю таблицу. После заполнения таблицы это будет выглядеть так:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Длина LCS между s1 и s2 будет равна таблице [5] [6] = 4 . Здесь 5 и 6 - длина s2 и s1 соответственно. Наш псевдокод будет:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
Сложность времени для этого алгоритма: O (mn), где m и n обозначает длину каждой строки.
Как узнать самую длинную общую подпоследовательность? Мы начнем с нижнего правого угла. Мы проверим, откуда это значение. Если значение идет по диагонали, то есть, если таблица [i-1] [j-1] равна таблице [i] [j] - 1 , мы нажимаем либо s2 [i], либо s1 [j] (оба одинаковы) и двигаться по диагонали. Если значение идет сверху, это означает, что если таблица [i-1] [j] равна таблице [i] [j] , мы переходим к вершине. Если значение идет слева, это означает, что если таблица [i] [j-1] равна таблице [i] [j] , мы перемещаемся влево. Когда мы достигнем самого левого или верхнего столбца, наш поиск заканчивается. Затем мы выставляем значения из стека и печатаем их. Псевдокод:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Следует отметить: если обе таблицы [i-1] [j] и таблица [i] [j-1] равны таблице [i] [j], а таблица [i-1] [j-1] не является равной таблице [i] [j] - 1 , для этого момента может быть два LCS. Этот псевдокод не рассматривает эту ситуацию. Вам придется решить эту проблему, чтобы найти несколько LCS.
Сложность времени для этого алгоритма: O (max (m, n)) .
Самая продолжительная подпоследовательность
Задача состоит в том, чтобы найти длину самой длинной подпоследовательности в заданном массиве целых чисел, так что все элементы подпоследовательности отсортированы в порядке возрастания. Например, длина самой длинной возрастающей подпоследовательности (LIS) для {15, 27, 14, 38, 26, 55, 46, 65, 85} равна 6, а самая длинная возрастающая подпоследовательность - {15, 27, 38, 55, 65, 85} . Опять же для {3, 4, -1, 0, 6, 2, 3} длины LIS равно 4, а подпоследовательность {-1, 0, 2, 3} . Для решения этой проблемы мы будем использовать динамическое программирование.
Возьмем второй пример: Item = {3, 4, -1, 0, 6, 2, 3} . Мы начнем с принятия массива dp того же размера нашей последовательности. dp [i] представляет длину LIS, если мы включим i- й элемент нашей исходной последовательности. В самом начале мы знаем, что для каждого элемента по крайней мере самая длинная возрастающая подпоследовательность имеет длину 1 . То есть, рассматривая единственный элемент. Итак, мы инициализируем массив dp с помощью 1 . У нас будут две переменные i и j . Первоначально i будет 1 и j будет 0 . Наш массив будет выглядеть так:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Число над массивом представляет собой соответствующий элемент нашей последовательности. Наша стратегия будет:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Это означает, что если элемент в i больше элемента в j , длина LIS, которая содержит элемент в j , будет увеличиваться на длину 1, если мы включим элемент в i с ним. В нашем примере для i = 1 и j = 0 элемент [i] больше, чем Item [j] . Итак, dp [i] = dp [j] + 1 . Наш массив будет выглядеть так:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
На каждом шаге мы увеличим j до i, а затем сбросим j на 0 и увеличиваем i . На данный момент j достиг i , поэтому мы увеличиваем i до 2 .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 2 , j = 0 элемент [i] не больше Item [j] , поэтому мы ничего не делаем и увеличиваем j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 2 , j = 1 , Item [i] не больше Item [j] , поэтому мы ничего не делаем, и поскольку j достиг своего предела, мы увеличиваем i и сбрасываем j на 0 .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 3 , j = 0 элемент [i] не больше Item [j] , поэтому мы ничего не делаем и увеличиваем j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 3 , j = 1 элемент [i] не больше Item [j] , поэтому мы ничего не делаем и увеличиваем j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 3 , j = 2 , элемент [i] больше, чем Item [j] , поэтому dp [i] = dp [j] + 1 . После этого, так как j достиг своего предела, снова мы сбрасываем j на 0 и увеличиваем i .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 4 и j = 0 элемент [i] больше, чем Item [j] , поэтому dp [i] = dp [j] + 1 . После этого мы увеличиваем j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 2 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 4 и j = 1 элемент [i] больше, чем Item [j] . Мы также можем заметить, что dp [i] = dp [j] + 1 предоставит нам 3 , что означает, что если мы возьмем LIS для Item [j] и добавим Item [i] с ним, мы получим лучшую LIS { 3,4,6}, чем до {3,6}. Итак, положим dp [i] = dp [j] + 1 . Затем мы увеличиваем j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Для i = 4 и j = 2 элемент [i] больше, чем Item [j] . Но для этого случая, если мы установим dp [i] = dp [j] + 1 , получим 2 , что {-1,6} не самое лучшее {3,4,6}, которое мы можем сделать, используя Item [ i] . Поэтому мы отказываемся от этого. Мы добавим условие к нашей стратегии, то есть:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
Мы увеличиваем j на 1 . Следуя этой стратегии, если мы закончим наш массив dp , он будет выглядеть так:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 3 | 4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Теперь мы будем проходить через этот массив и узнаем максимальное значение, которое будет длиной LIS. Наш псевдокод будет:
Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0 to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l
Сложность времени этого алгоритма равна O(n²) где n - длина последовательности.
Чтобы узнать исходную последовательность, нам нужно выполнить итерацию назад и сопоставить ее с нашей длиной. Процедура такова:
Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while
Временная сложность этого алгоритма: O(n) .
Самая длинная палиндромная подпоследовательность
С учетом строки, что является самой длинной палиндромной подпоследовательностью (LPS)? Возьмем строку agbdba . LPS этой строки является abdba длины 5 . Помните, что, поскольку мы ищем подпоследовательность , символы не обязательно должны быть непрерывными в исходной строке. Самая длинная палиндромная подстрока последовательности будет bdb длины 3 . Но мы сосредоточимся на подпоследовательности здесь. Мы будем использовать динамическое программирование для решения этой проблемы.
Сначала мы возьмем 2D-массив того же размера нашей исходной последовательности. Для нашего примера: S = "agbdba" , мы возьмем массив dp [6] [6] . Здесь dp [i] [j] представляет длину LPS, которую мы можем сделать, если мы рассмотрим символы из s [i] в s [j] . Например. если наша строка была aa , dp [0] [1] сохранит 2 . Теперь мы рассмотрим разную длину нашей строки и узнаем максимально возможную длину, которую мы можем сделать из нее.
Длина = 1 :
Здесь мы рассматриваем только 1 персонаж за раз. Итак, если бы у нас была строка длиной 1 , что у нас есть LPS? Конечно, ответ: 1 . Как его сохранить? dp [i] [j], где i равно j, представляет собой строку длиной 1 . Поэтому мы установим dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] 5] - 1 . Наш массив будет выглядеть так:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Длина = 2 :
На этот раз мы рассмотрим строки длины 2 . Теперь, рассматривая строки длины 2 , максимальная длина LPS может быть 2 тогда и только тогда, когда два символа строки одинаковы. Поэтому наша стратегия будет:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Если мы заполним наш массив по стратегии для Length = 2 , мы получим:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Длина = 3 :
Теперь мы смотрим на 3 символа за исходную строку. С этого момента LPS, который мы можем сделать из нашей строки, будет определяться:
- Если совпадение первого и последнего символов у нас будет иметь как минимум 2 элемента, из которых мы можем сделать LPS +, если мы исключим первый и последний символ, что самое лучшее, что мы можем сделать из оставшейся строки.
- Если первый и последний символы не совпадают, LPS, который мы можем сделать, будет получен либо от первого символа, либо от предыдущего символа, который мы уже вычислили.
Чтобы летать,
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
Если мы заполним массив dp для Length = 3 to Length = 6 , мы получим:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Это наш требуемый массив dp, а dp [0] [5] будет содержать длину LPS. Наша процедура будет выглядеть так:
Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
dp[i][i] := 1
end for
for i from 0 to (n-2)
if S[i] := S[i+1]
dp[i][i+1] := 2
else
dp[i][i+1] := 1
end if
end for
Length := 3
while Length <= n
for i from 0 to (n - Length)
j := i + Length - 1
if S[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
end for
Length := Length + 1
end while
Return dp[0][n-1]
Сложность времени этого алгоритма равна O(n²) , где n - длина данной строки. Самая длинная проблема Palindromic Subsequence тесно связана с самой длинной общей субпоследовательностью. Если мы берем вторую строку как обратную сторону первой строки и вычисляем длину и печатаем результат, это будет самая длинная палиндромная подпоследовательность данной строки. Сложность этого алгоритма также O(n²) .