Plus longue sous-séquence commune
Aligner deux chaînes avec une table de DP
Plus longue sous-séquence commune est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce qu'une sous-séquence ?
Une sous-séquence conserve les caractères dans leur ordre, mais peut en ignorer certains. À partir de 'abcde', vous pouvez prendre 'ace', mais jamais 'aec'.
L'objectif du LCS
Étant donné deux chaînes, la plus longue sous-séquence commune est la plus longue séquence qui apparaît dans les deux, dans le même ordre relatif.
Passer à une grille
Comparez les préfixes des deux chaînes. Un tableau à deux dimensions, basé sur leurs longueurs, transforme le problème en un DP classique sur une grille.
Définir l'état
Soit dp[i][j] la longueur du LCS des i premiers caractères de A et des j premiers caractères de B.
Lorsque les caractères correspondent
Si A[i-1] est égal à B[j-1], cette lettre commune prolonge le LCS. Ajoutez un à la valeur de la diagonale dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Lorsqu'ils diffèrent
Si les lettres diffèrent, retirez un caractère de l'une ou l'autre chaîne et conservez le meilleur résultat. Prenez le maximum des deux voisins.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Le cas de base
Un préfixe vide ne partage aucun caractère, la longueur du LCS vaut donc zéro. La ligne 0 et la colonne 0 restent entièrement remplies de zéros.
dp = [[0] * (m+1) for _ in range(n+1)]Une ligne et une colonne supplémentaires
Dimensionner le tableau en n+1 par m+1 fournit une bordure de zéros gratuite. Cela évite les vérifications de limites gênantes sur les bords.
Le remplir
Parcourez i et j à partir de 1. Chaque cellule n'a besoin que des valeurs du dessus, de la gauche et de la diagonale, qui sont déjà calculées.
for i in range(1, n+1):
for j in range(1, m+1):
...Lire la longueur
La longueur complète du LCS se trouve dans le coin. La réponse est dp[n][m] lorsque toutes les cellules sont remplies.
length = dp[n][m]Complexité
Vous visitez chaque cellule une seule fois, le travail s'effectue donc en temps et en mémoire O(n fois m). Cela suffit largement pour des chaînes de quelques milliers de caractères.
Vérification rapide
Les caractères actuels A[i-1] et B[j-1] sont égaux. Quelle mise à jour est correcte ?
Récapitulatif : LCS
Construisez un tableau de n+1 par m+1 : en cas de correspondance, ajoutez un à la diagonale ; sinon, prenez le maximum des voisins. Le coin contient la longueur. 🔗
Questions Fréquemment Posées
La leçon « Plus longue sous-séquence commune » est-elle gratuite ?
Oui — le texte complet de « Plus longue sous-séquence commune » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Plus longue sous-séquence commune » ?
Aligner deux chaînes avec une table de DP Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Plus longue sous-séquence commune » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Compter les chemins sur une grille
- Somme minimale d’un chemin avec obstacles
- Plus longue sous-séquence commune
- Distance d’édition étape par étape