La plus longue sous-séquence commune: Algorithme de programmation dynamique

Cette séance de cours couvre le concept de la plus longue sous-séquence commune (LCS) entre deux séquences, expliquant qu'une sous-séquence commune aux deux doit être dans l'ordre mais pas nécessairement consécutive. L'instructeur introduit la méthode de force brute, puis plonge dans l'algorithme de programmation dynamique, détaillant la sous-structure optimale et la formulation récursive. L'approche ascendante du LCS est discutée, en soulignant l'importance d'identifier les choix et la sous-structure optimale, d'écrire la solution optimale de manière récursive et de résoudre efficacement la récursion. La séance de cours se termine par un appel à la pratique pour maîtriser les concepts.