Somme minimale pour traverser un carré⚓︎
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 côté gauche au côté droit,
- les seuls déplacements autorisés sont →, ↓, ↑
Le chemin marqué en gras donne une somme de \(994\) qui est ici le minimum possible pour cet exercice.
Écrire une fonction telle que somme_minimale_2(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 = [[5, 2, 3], [2, 0, 5], [3, 2, 1],]
>>> somme_minimale_2(grille)
5
>>> grille = [
... [9, 9, 0, 9, 9],
... [3, 1, 9, 9, 9],
... [5, 1, 9, 1, 3],
... [7, 1, 9, 1, 9],
... [9, 1, 1, 1, 9],
... ]
>>> somme_minimale_2(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_2(grille)
994
def sommepy-undminimalepy-und2(grille):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[5, 2, 3], [2, 0, 5], [3, 2, 1]]bksl-nlassert sommepy-undminimalepy-und2(grille) == 5bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [9, 9, 0, 9, 9],bksl-nl [3, 1, 9, 9, 9],bksl-nl [5, 1, 9, 1, 3],bksl-nl [7, 1, 9, 1, 9],bksl-nl [9, 1, 1, 1, 9],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(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-und2(grille) == 994bksl-nlbksl-nldef sommepy-undminimalepy-und2(grille):bksl-nl n = len(grille)bksl-nl colonne = [grille[i][0] for i in range(n)]bksl-nl for j in range(1, n):bksl-nl colonne[0] += grille[0][j]bksl-nl for i in range(1, n):bksl-nl colonne[i] = grille[i][j] + min(colonne[i-1], colonne[i])bksl-nl for i in range(n-2, -1, -1):bksl-nl colonne[i] = min(colonne[i], colonne[i+1] + grille[i][j])bksl-nl return min(colonne)bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlgrille = [[5, 2, 3], [2, 0, 5], [3, 2, 1]]bksl-nlassert sommepy-undminimalepy-und2(grille) == 5bksl-nlbksl-nlbksl-nlgrille = [bksl-nl [9, 9, 0, 9, 9],bksl-nl [3, 1, 9, 9, 9],bksl-nl [5, 1, 9, 1, 3],bksl-nl [7, 1, 9, 1, 9],bksl-nl [9, 1, 1, 1, 9],bksl-nl]bksl-nlassert sommepy-undminimalepy-und2(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-und2(grille) == 994bksl-nlbksl-nl
A
Z