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

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

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

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

🐍 Console Python

>>> grille = [[1, 5, 9], [10, 3, 5], [10, 2, 3]]
>>> somme_minimale_1(grille)
14

\[ \begin{pmatrix} \mathbf{131} & 673 & 234 & 103 & 18 \\ \mathbf{201} & \mathbf{96} & \mathbf{342} & 965 & 150 \\ 630 & 803 & \mathbf{746} & \mathbf{422} & 111 \\ 537 & 699 & 497 & \mathbf{121} & 956 \\ 805 & 732 & 524 & \mathbf{37} & \mathbf{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_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