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 →, ↓, ↑

\[\begin{pmatrix} 131 & 673 & \mathbf{234} & \mathbf{103} & \mathbf{18} \\ \mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331\\ \end{pmatrix}\]

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

\[\begin{pmatrix} 5 & 2 & 3 \\ \mathbf 2 & \mathbf 0 & 2 \\ 3 & \mathbf 2 & \mathbf 1 \\ \end{pmatrix}\]

🐍 Console Python

>>> grille = [[5, 2, 3], [2, 0, 5], [3, 2, 1],]
>>> somme_minimale_2(grille)
5

\[\begin{pmatrix} 9 & 9 & 0 & 9 & 9 \\ \mathbf{3} & \mathbf{1} & 9 & 9 & 9 \\ 5 & \mathbf{1} & 9 & \mathbf{1} & \mathbf{3} \\ 7 & \mathbf{1} & 9 & \mathbf{1} & 9\\ 9 & \mathbf{1} & \mathbf{1} & \mathbf{1} & 9\\ \end{pmatrix}\]

🐍 Console Python

>>> 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

\[\begin{pmatrix} 131 & 673 & \mathbf{234} & \mathbf{103} & \mathbf{18} \\ \mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 331\\ \end{pmatrix}\]

🐍 Console Python

>>> 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