Programmation dynamique et recherche textuelle

La programmation dynamique résout des problèmes en les décomposant en sous-problèmes qui se chevauchent, et en stockant les résultats intermédiaires pour éviter de les recalculer. L'exemple le plus classique est le calcul de Fibonacci : l'approche récursive naïve recalcule fib(3) de nombreuses fois (complexité exponentielle O(2ⁿ)), tandis que la mémoïsation stocke les résultats déjà calculés dans un dictionnaire (complexité O(n)). Le rendu de monnaie est un autre problème classique : trouver le nombre minimum de pièces pour atteindre une somme donnée. La recherche textuelle naïve consiste à chercher un motif dans un texte en testant chaque position de départ possible. Pour un texte de longueur n et un motif de longueur m, la complexité est O(n × m) dans le pire cas. L'algorithme de Boyer-Moore améliore cela en pratique en sautant des positions.