Plus Longue Sous-séquence Commune (LCS)
Programmation dynamique classique
Enonce
Calculer la LCS de deux chaînes. Retourner la sous-séquence elle-même (pas seulement sa longueur).
Exemple : LCS("ABCBDAB", "BDCAB") = "BCAB" (longueur 4).
Signature attendue
def lcs(X: str, Y: str) -> str:Exemples
lcs("ABCBDAB", "BDCAB")→BCABlcs("AGGTAB", "GXTXAYB")→GTABlen(lcs("ABCBDAB", "BDCAB"))→4
📖 Rappel de cours
La LCS (Longest Common Subsequence) de deux séquences est la plus longue sous-séquence commune (pas nécessairement contiguë).
Récurrence :
$dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & \text{si } X[i-1]=Y[j-1] \\ \max(dp[i-1][j],\, dp[i][j-1]) & \text{sinon} \end{cases}$
$dp[i][j]$ = longueur de la LCS de $X[0..i-1]$ et $Y[0..j-1]$.
⚠ Le piège : Le tableau a une ligne et une colonne de plus que les longueurs des chaînes : la ligne 0 correspond à la chaîne vide. Décaler les indices est l'erreur qui fait échouer l'exercice. Et pour reconstruire la sous-séquence — et pas seulement sa longueur — il faut remonter le tableau depuis le coin, ce que l'énoncé demande ici.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Algorithme de Boyer-Moore simplifié
- Algorithme glouton : rendu de monnaie
- Sac à dos (Programmation Dynamique)
- Détection de Cycle (Floyd)
- Arbres Binaires — Parcours et Hauteur
- Arbre Binaire de Recherche (ABR)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.