Prépa Code Connexion Inscription

On considere une matrice M de taille n x m contenant des entiers positifs. On part de la case en haut a gauche (0, 0) et on veut atteindre la case en bas a droite (n-1, m-1). A chaque etape, on ne peut se deplacer que vers la droite ou vers le bas.

Ecrire une fonction chemin_min(M) qui renvoie le cout minimal d'un chemin allant de (0, 0) a (n-1, m-1), ou le cout d'un chemin est la somme des valeurs des cases traversees.

On definit C(i, j) le cout minimal pour atteindre la case (i, j) : - C(0, 0) = M[0][0] - C(i, 0) = C(i-1, 0) + M[i][0] (premiere colonne : on ne peut venir que d'en haut) - C(0, j) = C(0, j-1) + M[0][j] (premiere ligne : on ne peut venir que de la gauche) - C(i, j) = M[i][j] + min(C(i-1, j), C(i, j-1)) sinon