Programmation dynamique : LCS par tabulation

1. De la récurrence à la tabulation

Rappelons la relation de récurrence que nous avons établie pour c[i, j], la longueur de la LCS des préfixes X_i et Y_j :

Une implémentation récursive directe serait inefficace à cause des nombreux calculs redondants. L'approche par tabulation résout ce problème en calculant les solutions des sous-problèmes une seule fois et en les stockant dans une table, généralement un tableau 2D.

L'idée est de remplir cette table, que nous nommerons DP, de dimensions (m+1) x (n+1) (où m et n sont les longueurs de X et Y), en commençant par les cas de base (i=0 ou j=0) et en progressant vers la solution finale DP[m][n].

La relation de récurrence nous indique que pour calculer DP[i][j], nous avons besoin de valeurs déjà calculées : DP[i-1][j-1], DP[i-1][j], et DP[i][j-1]. Un ordre de calcul qui garantit que ces dépendances sont toujours satisfaites est un simple balayage de la table, ligne par ligne, ou colonne par colonne.

2. Remplissage de la table : une approche visuelle

Pour bien comprendre le processus, rien ne vaut une démonstration. La vidéo suivante explique comment initialiser la table et la remplir pas à pas en se basant sur la récurrence.

Pour formaliser ce que vous venez de voir, le document ci-dessous présente l'algorithme de manière textuelle et rigoureuse. Notez que le problème de la "distance d'édition" y est traité, mais la structure de l'algorithme et le remplissage du tableau E sont en tout point analogues à ce que nous faisons pour la LCS.

3. Implémentation en Python

Nous sommes maintenant prêts à traduire cet algorithme en code Python. Étant donné votre aisance avec ce langage, l'implémentation devrait être directe. Il faut néanmoins être vigilant sur la gestion des indices. La convention mathématique utilise des indices de 1 à m et n, tandis que Python utilise des indices de 0 à m-1 et n-1.

Une pratique courante et robuste consiste à créer une table dp de taille (m+1) x (n+1). Ainsi, dp[i][j] correspond bien à la LCS des préfixes de longueur i et j, et les caractères correspondants dans les chaînes sont X[i-1] et Y[j-1].

La section suivante de la vidéo propose une implémentation Python claire et commentée.

Voici une version de l'implémentation qui suit un parcours "naturel" (de haut en bas), ce qui peut être plus simple à raisonner lors d'une épreuve.

def lcs_length(X: str, Y: str) -> int:
    """
    Calcule la longueur de la plus longue sous-séquence commune
    entre deux chaînes X et Y par tabulation.
    """
    m = len(X)
    n = len(Y)




    # Initialisation d'une table (m+1) x (n+1) avec des zéros.
    # dp[i][j] stockera la longueur de la LCS de X[0..i-1] et Y[0..j-1].
    # Les cas de base (i=0 ou j=0) sont automatiquement gérés par cette initialisation.
    dp = [[0] * (n + 1) for _ in range(m + 1)]




    # Remplissage de la table de manière ascendante.
    for i in range(1, m + 1):
        for j in range(1, n + 1):



            # Cas 1: les derniers caractères sont identiques
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]



            # Cas 2: les derniers caractères sont différents
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])




    # La solution se trouve dans la dernière case.
    return dp[m][n]




# Exemple
X = "AGGTAB"
Y = "GXTXAYB"
print(f"La longueur de la LCS est : {lcs_length(X, Y)}") # Devrait afficher 4

Analyse de complexité

• Complexité temporelle : L'algorithme est dominé par deux boucles imbriquées qui s'exécutent m et n fois. Le travail à l'intérieur des boucles est en temps constant. La complexité temporelle est donc $O(m\times n)$.
• Complexité spatiale : Nous stockons une table de dimensions (m+1) x (n+1). La complexité spatiale est donc $O(m\times n)$.

Il est bon de savoir que si seule la longueur est requise, la complexité spatiale peut être réduite à $O(\min (m,n))$, car le calcul de la ligne i ne dépend que de la ligne i-1. C'est une optimisation classique, mais qui complique la reconstruction de la séquence que nous verrons plus tard.

4. Exercice d'application

Pour vous assurer d'avoir bien assimilé la méthode, je vous propose de la mettre en œuvre vous-même.

1. Écrivez à la main la table de programmation dynamique pour les deux chaînes suivantes :

   • X = "ABCBDAB"
   • Y = "BDCABA"

   Quelle est la longueur de la LCS que vous trouvez ?

2. Implémentez la fonction lcs_length en Python sans regarder le code ci-dessus, puis testez-la avec ces deux chaînes. Votre résultat doit correspondre à celui que vous avez trouvé manuellement.

Cet exercice en deux temps renforce le lien essentiel entre le mécanisme de remplissage de la table et son implémentation effective.

Conclusion

Félicitations, vous avez maintenant implémenté une solution complète pour calculer la longueur de la plus longue sous-séquence commune.

Points clés à retenir :

• L'approche par tabulation transforme la relation de récurrence en un algorithme itératif, éliminant les appels récursifs redondants.
• La clé est de remplir une table 2D dans un ordre qui respecte les dépendances de calcul (généralement de haut en bas, de gauche à droite).
• L'implémentation en Python demande une attention particulière aux indices pour faire correspondre la table dp[i][j] aux préfixes X[0..i-1] et Y[0..j-1].
• La solution standard a une complexité temporelle et spatiale de $O(m\times n)$.

Nous savons maintenant calculer la longueur de la LCS. Mais comment obtenir la sous-séquence elle-même ? Dans notre prochaine leçon, nous aborderons la dernière étape : la reconstruction de la solution. Nous verrons comment "remonter" le chemin dans la table dp pour construire une des LCS possibles.