Un indice pour améliorer l'algorithme

Il est possible de voir le problème de la LCS comme la recherche d'un chemin de coût minimum dans un graphe bien choisi. Sur l'exemple des suites
Les suites
on a le graphe suivant :
Le graphe de poids
Le poids des arêtes diagonales est nul, et celui des autres arêtes est 1.