La sous-séquence la plus longue et la BST optimale

Cette séance de cours couvre la formulation récursive du problème de la sous-séquence commune la plus longue (LCS), en discutant de la mise en œuvre naïve et de l'approche ascendante pour trouver LCS. Il se penche également sur l'enregistrement des solutions optimales, la présentation du pseudocode et l'analyse pour LCS, et l'impression de la solution. En outre, il introduit le concept d'arbres de recherche binaires optimaux (BST), expliquant comment construire une BST avec un coût de recherche minimal en utilisant des probabilités. Des exemples sont fournis pour illustrer les concepts, soulignant que la BST optimale peut ne pas avoir la plus petite hauteur ou la clé de probabilité la plus élevée à la racine. La séance de cours se termine par des discussions sur le coût de recherche des clés dans une BST optimale et la sous-structure optimale pour construire un arbre de recherche binaire.