dynamic-programming
Algorithmes liés à la sous-séquence
Recherche…
La plus longue sous-séquence commune
L'une des implémentations les plus importantes de la programmation dynamique consiste à trouver la sous- séquence commune la plus longue . Définissons d'abord certaines des terminologies de base.
Sous-séquence:
Une sous-séquence est une séquence qui peut être dérivée d'une autre séquence en supprimant certains éléments sans modifier l'ordre des éléments restants. Disons que nous avons une chaîne ABC . Si nous effaçons zéro ou un ou plusieurs caractères de cette chaîne, nous obtenons la sous-séquence de cette chaîne. Les sous-séquences de la chaîne ABC seront donc { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Même si nous supprimons tous les caractères, la chaîne vide sera également une sous-séquence. Pour trouver la sous-séquence, pour chaque caractère d'une chaîne, nous avons deux options: soit nous prenons le caractère, soit nous ne le faisons pas. Donc, si la longueur de la chaîne est n , il y a 2 n sous- séquences de cette chaîne.
Plus longue sous-séquence commune:
Comme son nom l'indique, de toutes les sous-séquences communes entre deux chaînes, la plus longue sous-séquence commune (LCS) est celle qui a la longueur maximale. Par exemple: Les sous-séquences communes entre "HELLOM" et "HMLD" sont "H" , "HL" , "HM", etc. Ici, "HLL" est la plus longue sous-séquence commune de longueur 3.
Méthode Brute-Force:
Nous pouvons générer toutes les sous-séquences de deux chaînes en utilisant le backtracking . Ensuite, nous pouvons les comparer pour trouver les sous-séquences communes. Après nous aurons besoin de trouver celui avec la longueur maximale. Nous avons déjà vu que, il y a 2 n sous- séquences d'une chaîne de longueur n . Il faudrait des années pour résoudre le problème si notre n traverse 20-25.
Méthode de programmation dynamique:
Abordons notre méthode avec un exemple. Supposons que nous ayons deux chaînes abcdaf et acbcf . Notons ceux-ci avec s1 et s2 . Donc, la plus longue sous-séquence commune de ces deux chaînes sera "abcf" , qui a la longueur 4. Encore une fois, je vous le rappelle, les sous-séquences ne doivent pas nécessairement être continues dans la chaîne. Pour construire "abcf" , nous avons ignoré "da" dans s1 et "c" dans s2 . Comment trouvons-nous cela en utilisant la programmation dynamique?
Nous allons commencer avec une table (un tableau 2D) ayant tous les caractères de s1 dans une ligne et tous les caractères de s2 dans la colonne. Ici, la table est indexée sur 0 et nous mettons les caractères de 1 à plus. Nous allons parcourir la table de gauche à droite pour chaque ligne. Notre table ressemblera à:
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 | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Ici, chaque ligne et chaque colonne représente la longueur de la plus longue sous-séquence commune entre deux chaînes si nous prenons les caractères de cette ligne et de cette colonne et les ajoutons au préfixe précédent. Par exemple: La table [2] [3] représente la longueur de la plus longue sous-séquence commune entre "ac" et "abc" .
La colonne 0-th représente la sous-séquence vide de s1 . De même, la 0ème ligne représente la sous-séquence vide de s2 . Si nous prenons une sous-séquence vide d'une chaîne et essayons de la faire correspondre à une autre chaîne, quelle que soit la longueur de la seconde sous-chaîne, la sous-séquence commune aura une longueur de 0. Nous pouvons donc remplir les lignes 0 et 0 et les colonnes 0 avec des 0. On a:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Commençons. Lorsque nous remplissons la table [1] [1] , nous nous demandons si nous avons une chaîne a et une autre chaîne a et rien d'autre, quelle sera la plus longue sous-séquence commune ici? La longueur du LCS sera de 1. Regardons maintenant le tableau [1] [2] . Nous avons une chaîne ab et une chaîne a . La longueur du LCS sera 1. Comme vous pouvez le voir, le reste des valeurs sera également 1 pour la première ligne car il ne considère que la chaîne a avec abcd , abcda , abcdaf . Donc, notre table ressemblera à:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Pour la ligne 2, qui inclura désormais c . Pour le tableau [2] [1], nous avons ac d'un côté et a de l'autre côté. La longueur du LCS est donc de 1. Où avons-nous obtenu ce 1? Du haut, qui désigne le LCS a entre deux sous-chaînes. Donc, ce que nous disons, c'est que si s1 [2] et s2 [1] ne sont pas identiques, alors la longueur du LCS sera le maximum de la longueur de LCS en haut ou à gauche . En prenant la longueur du LCS en haut, cela signifie que nous ne prenons pas le caractère actuel de s2 . De même, la prise en compte de la longueur du LCS à gauche indique que nous ne prenons pas le caractère actuel de s1 pour créer le LCS. On a:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Donc, notre première formule sera:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Passons maintenant à la table [2] [2], nous avons la chaîne ab et ac . Puisque c et b ne sont pas les mêmes, nous mettons le maximum du haut ou de gauche ici. Dans ce cas, c'est encore 1. Après cela, pour la Table [2] [3], nous avons la chaîne abc et ac . Cette fois, les valeurs actuelles des lignes et des colonnes sont identiques. Maintenant, la longueur de LCS sera égale à la longueur maximale de LCS jusqu'à présent. 1. Comment pouvons-nous obtenir la longueur maximale de LCS jusqu'à présent? Nous vérifions la valeur diagonale, qui représente la meilleure correspondance entre ab et a . A partir de cet état, pour les valeurs actuelles, nous avons ajouté un caractère supplémentaire à s1 et s2, qui se sont avérés identiques. Ainsi, la longueur de LCS va bien sûr augmenter. Nous allons mettre 1 + 1 = 2 dans le tableau [2] [3] . On a,
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Donc, notre deuxième formule sera:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Nous avons défini les deux cas. En utilisant ces deux formules, nous pouvons remplir toute la table. Après avoir rempli la table, cela ressemblera à ceci:
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 |
+-----+-----+-----+-----+-----+-----+-----+-----+
La longueur du LCS entre s1 et s2 sera la table [5] [6] = 4 . Ici, 5 et 6 sont respectivement la longueur de s2 et s1 . Notre pseudo-code sera:
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]
La complexité temporelle de cet algorithme est la suivante: O (mn) où m et n désignent la longueur de chaque chaîne.
Comment pouvons-nous trouver la plus longue sous-séquence commune? Nous allons commencer par le coin inférieur droit. Nous allons vérifier d'où vient la valeur. Si la valeur provient de la diagonale, c'est-à-dire si la table [i-1] [j-1] est égale à la table [i] [j] - 1 , on appuie sur s2 [i] ou s1 [j] sont les mêmes) et se déplacer en diagonale. Si la valeur vient du haut, cela signifie que si la table [i-1] [j] est égale à la table [i] [j] , nous passons au sommet. Si la valeur vient de gauche, cela signifie que si la table [i] [j-1] est égale à la table [i] [j] , nous nous déplaçons vers la gauche. Lorsque nous atteignons la colonne la plus à gauche ou la plus haute, notre recherche se termine. Ensuite, nous affichons les valeurs de la pile et les imprimons. Le pseudo-code:
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
Point à noter: si le tableau [i-1] [j] et le tableau [i] [j-1] sont égaux au tableau [i] [j] et le tableau [i-1] [j-1] n’est pas égale à la table [i] [j] - 1 , il peut y avoir deux LCS pour ce moment. Ce pseudo-code ne considère pas cette situation. Vous devrez résoudre ce problème de manière récursive pour trouver plusieurs LCS.
La complexité temporelle de cet algorithme est la suivante: O (max (m, n)) .
Plus longue sous-séquence croissante
La tâche consiste à trouver la longueur de la plus longue sous-séquence dans un tableau d'entiers donné, de sorte que tous les éléments de la sous-séquence soient triés dans l'ordre croissant. Par exemple, la longueur de la plus longue sous-séquence croissante (LIS) pour {15, 27, 14, 38, 26, 55, 46, 65, 85} est 6 et la plus longue sous-séquence croissante est {15, 27, 38, 55, 65, 85} . Encore une fois pour {3, 4, -1, 0, 6, 2, 3} longueur de LIS est 4 et la sous-séquence est {-1, 0, 2, 3} . Nous utiliserons une programmation dynamique pour résoudre ce problème.
Prenons le deuxième exemple: Item = {3, 4, -1, 0, 6, 2, 3} . Nous commencerons par prendre le tableau dp de la même taille que notre séquence. dp [i] représente la longueur du LIS si nous incluons le i ème élément de notre séquence originale. Au tout début, nous savons que pour chaque élément au moins la plus longue sous-séquence croissante est de longueur 1 . C'est en considérant l'élément unique lui-même. Nous allons donc initialiser le tableau dp avec 1 . Nous aurons deux variables i et j . Au départ, je serai 1 et j sera 0 . Notre tableau ressemblera à:
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
Le nombre au-dessus du tableau représente l'élément correspondant de notre séquence. Notre stratégie sera:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Cela signifie que si element at i est plus grand que element en j , la longueur du LIS qui contient element en j augmentera de longueur 1 si on inclut element at i avec elle. Dans notre exemple, pour i = 1 et j = 0 , l' élément [i] est supérieur à l' élément [j] . Donc dp [i] = dp [j] + 1 . Notre tableau ressemblera à:
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
A chaque étape, nous augmenterons j jusqu'à i puis réinitialiser j à 0 et incrémenter i . Pour l'instant, j a atteint i , donc nous incrémentons 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
Pour i = 2 , j = 0 , Item [i] n'est pas supérieur à Item [j] , nous ne faisons donc rien et incrémentons 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
Pour i = 2 , j = 1 , Item [i] n'est pas plus grand que Item [j] , nous ne faisons donc rien et comme j a atteint sa limite, nous incrémentons i et réinitialisons 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
Pour i = 3 , j = 0 , Item [i] n'est pas supérieur à Item [j] , donc nous ne faisons rien et incrémentons 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
Pour i = 3 , j = 1 , Item [i] n'est pas plus grand que Item [j] , donc nous ne faisons rien et incrémentons 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
Pour i = 3 , j = 2 , Item [i] est plus grand que Item [j] , donc dp [i] = dp [j] + 1 . Après cela, j ayant atteint sa limite, nous remettons encore j à 0 et incrémentons 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
Pour i = 4 et j = 0 , Item [i] est supérieur à Item [j] , donc dp [i] = dp [j] + 1 . Après cela, nous incrémentons 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
Pour i = 4 et j = 1 , l' item [i] est supérieur à l' item [j] . Nous pouvons également remarquer que dp [i] = dp [j] + 1 nous fournira 3 , ce qui signifie que si nous prenons le LIS pour Item [j] et ajoutons Item [i] , nous aurons un meilleur LIS { 3,4,6} qu'auparavant {3,6}. Nous définissons donc dp [i] = dp [j] + 1 . Ensuite, nous incrémentons 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
Pour i = 4 et j = 2 , Item [i] est supérieur à Item [j] . Mais dans ce cas, si nous définissons dp [i] = dp [j] + 1 , nous aurons 2 , ce qui correspond à {-1,6} pas le meilleur {3,4,6} que nous pouvons faire avec Item [ i] . Donc, nous jetons celui-ci. Nous ajouterons une condition à notre stratégie, à savoir:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
Nous incrémentons j de 1 . Suivant cette stratégie, si nous complétons notre tableau dp , cela ressemblera à ceci:
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
Nous allons maintenant parcourir ce tableau et trouver la valeur maximale, qui sera la longueur du LIS. Notre pseudo-code sera:
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
La complexité temporelle de cet algorithme est O(n²) où n est la longueur de la séquence.
Pour trouver la séquence originale, nous devons effectuer une itération en arrière et la comparer à notre longueur. La procédure est la suivante:
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
La complexité temporelle de cet algorithme est la suivante: O(n) .
La plus longue sous-séquence palindromique
Étant donné une chaîne, quelle est la plus longue sous-séquence palindromique (LPS)? Prenons une chaîne agbdba . Le LPS de cette chaîne est abdba de longueur 5 . Rappelez-vous, puisque nous recherchons des sous- séquences , les caractères ne doivent pas nécessairement être continus dans la chaîne d'origine. La plus longue sous - chaîne palindromique de la séquence serait bdb de longueur 3 . Mais nous allons nous concentrer sur la sous- séquence ici. Nous allons utiliser une programmation dynamique pour résoudre ce problème.
Au début, nous prendrons un tableau 2D de la même dimension de notre séquence originale. Pour notre exemple: S = "agbdba" , nous prendrons le tableau dp [6] [6] . Ici, dp [i] [j] représente la longueur du LPS que nous pouvons faire si nous considérons les caractères de s [i] à s [j] . Par exemple. si notre chaîne était aa , dp [0] [1] stockerait 2 . Nous allons maintenant considérer différentes longueurs de notre chaîne et trouver la longueur la plus longue possible.
Longueur = 1 :
Ici, nous considérons que 1 caractère à la fois. Donc, si nous avions une chaîne de longueur 1 , quel est le LPS que nous pouvons avoir? Bien sûr, la réponse est 1 . Comment le stocker? dp [i] [j] où i est égal à j représente une chaîne de longueur 1 . Nous allons donc dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] [ 5] à 1 . Notre tableau ressemblera à:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Longueur = 2 :
Cette fois, nous considérerons des chaînes de longueur 2 . Maintenant, en considérant les chaînes de longueur 2 , la longueur maximale de LPS peut être 2 si et seulement si les deux caractères de la chaîne sont identiques. Notre stratégie sera donc la suivante:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Si nous remplissons notre tableau en suivant la stratégie pour Length = 2 , nous obtiendrons:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Longueur = 3 :
Maintenant, nous regardons 3 caractères à la fois pour notre chaîne d'origine. A partir de maintenant, le LPS que nous pouvons créer à partir de notre chaîne sera déterminé par:
- Si le premier et le dernier personnage correspondent, nous aurons au moins 2 éléments à partir desquels nous pourrons créer le LPS + si nous excluons le premier et le dernier caractère, quel que soit le meilleur que nous puissions tirer de la chaîne restante.
- Si les premier et dernier caractères ne correspondent pas, le LPS que nous pouvons faire proviendra soit de l'exclusion du premier caractère, soit du dernier caractère, que nous avons déjà calculé.
Pour l'été,
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
Si nous remplissons le tableau dp pour Length = 3 à Length = 6 , nous aurons:
+---+---+---+---+---+---+---+
| | 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 |
+---+---+---+---+---+---+---+
Ceci est notre tableau dp requis et dp [0] [5] contiendra la longueur du LPS. Notre procédure ressemblera à:
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]
La complexité temporelle de cet algorithme est O(n²) , où n est la longueur de notre chaîne donnée. Le plus long problème de sous-séquence palindromique est étroitement lié à la sous-séquence commune la plus longue. Si nous prenons la deuxième chaîne comme l'inverse de la première chaîne et calculons la longueur et imprimons le résultat, ce sera la plus longue sous-séquence palindromique de la chaîne donnée. La complexité de cet algorithme est également O(n²) .