Algorithme Python

Bonjour,
J’ai une question à propos des fonctions décrites dans le notebook Python. Dans la partie “L’algorithme récursif -> L’algorithme”, il est dit que :
" C’est pourquoi dans notre cas la formule principale est

cost (i, j) = min ( cost(i-1, j-1) + substitution(dna1[i-1], dna2[j-1]),
                    ...)

et non pas substitution(dna1[i], dna2[j])"
Je ne comprends pas pourquoi on ne fait pas substitution(dna1[i], dna2[j]), puisque je pensais que le coût du point (1,1) par exemple est le minimum de (coût du point (0,0) + coût de substitution (1,1) , coût du point(0,1)+ coût d’insertion , coût du point(1,0)+ coût d’insertion).

Dans la partie “Analyse de complexité”
il est écrit nw(dna1, dna2, i-1, j-1) + (dna1[i] != dna2[j]), donc dans cet algorithme, il n’est plus notifié les i-1 et j-1.
Est-ce que quelqu’un pourrait m’aider à comprendre ce point ?
Merci beaucoup par avance!

bonjour
pardon pour le temps de réponse…

comme il est dit c’est un problème de poteaux
si vous reprenez la figure, les points sur les lignes en haut et à gauche sont initialisés comme indiqué

prenez maintenant le cas du tout dernier point traité, en bas à droite, il est de coordonnées (3, 2); mais dna1 = 'ABC' et dna2 = 'AB'
vous voyez ici que dna1[i] donnerait dna1[3] qui n’est pas défini car les indices en Python commencent à 0

Merci beaucoup pour votre réponse, aucun souci pour le délai.
J’ai du mal à bien comprendre, je suis désolée.
Est-ce que pour vous le point (0,0) correspond à la “substitution” (qui n’est est pas une ici) A (de dna1) en A (de dna2) dans votre exemple ?
Merci encore par avance !

le point (0,0) correspond à la distance entre la chaine vide et la chaine vide, c’est pourquoi sa valeur est 0; le point (0, 1) correspond à la distance entre la chaine vide et la chaine A, donc un ajout, ici 1; etc…
le point (1, 1) correspond à la distance entre A et A - donc 0
du coup le dernier en bas à droite correspond toujours à la distance entre les deux chaines en entrée

Merci beaucoup pour votre réponse, c’est très clair maintenant pour moi !