Somme minimale pour traverser un carré en diagonale⚓︎
Une grille carrée étant donnée, remplie d'entiers positifs, on souhaite traverser le carré avec une somme minimale des entiers rencontrés.
Pour cet exercice,
- on souhaite aller du coin supérieur gauche au coin inférieur droit,
- les seuls déplacements autorisés sont →, ↓
Le chemin marqué en gras donne une somme de \(2427\) qui est ici le minimum possible pour cet exercice.
Écrire une fonction telle que somme_minimale_1(grille)
renvoie la somme minimale spécifiée plus haut. On garantit que la grille
est carrée et remplie d'entiers positifs.
Exemples
>>> grille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]
>>> somme_minimale_1(grille)
14
>>> grille = [
... [131, 673, 234, 103, 18],
... [201, 96, 342, 965, 150],
... [630, 803, 746, 422, 111],
... [537, 699, 497, 121, 956],
... [805, 732, 524, 37, 331],
... ]
>>> somme_minimale_1(grille)
2427
def sommepy-undminimalepy-und1(grille):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]bksl-nlassert sommepy-undminimalepy-und1(grille) == 14bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [131, 673, 234, 103, 18],bksl-nl [201, 96, 342, 965, 150],bksl-nl [630, 803, 746, 422, 111],bksl-nl [537, 699, 497, 121, 956],bksl-nl [805, 732, 524, 37, 331],bksl-nl]bksl-nlassert sommepy-undminimalepy-und1(grille) == 2427bksl-nlbksl-nldef sommepy-undminimalepy-und1(grille):bksl-nl n = len(grille)bksl-nl sommes = []bksl-nl cumul = 0bksl-nl for x in grille[0]:bksl-nl cumul += xbksl-nl sommes.append(cumul)bksl-nl for i in range(1, n):bksl-nl sommes[0] = sommes[0] + grille[i][0]bksl-nl for j in range(1, n):bksl-nl sommes[j] = grille[i][j] + min(sommes[j], sommes[j - 1])bksl-nl return sommes[-1]bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]bksl-nlassert sommepy-undminimalepy-und1(grille) == 14bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [131, 673, 234, 103, 18],bksl-nl [201, 96, 342, 965, 150],bksl-nl [630, 803, 746, 422, 111],bksl-nl [537, 699, 497, 121, 956],bksl-nl [805, 732, 524, 37, 331],bksl-nl]bksl-nlassert sommepy-undminimalepy-und1(grille) == 2427bksl-nlbksl-nl
A
Z