Meilleur parcours dans une grille (variante dynamique)

Il est question ici de l'exercice 2 du sujet 0 de l'épreuve terminale de NSI. Dans le sujet, on aborde le problème à la façon de la programmation dynamique. Mais, à la dernière question, on implémente en utilisant une récurrence ce qui n'est pas la meilleure façon de faire. On tente ici l'approche dynamique.

Je reprends les premières questions à l'identique

Présentation

On considère un tableau de nombres de n lignes et p colonnes.
Les lignes sont numérotées de 0 à n – 1 et les colonnes sont numérotées de 0 à p – 1.
La case en haut à gauche est repérée par (0, 0) et la case en bas à droite par (n – 1, p – 1).
On appelle chemin une succession de cases allant de la case (0, 0) à la case (n – 1, p – 1), en n'autorisant que des déplacements case par case : soit vers la droite, soit vers le bas.
On appelle somme d'un chemin la somme des entiers situés sur ce chemin.

Par exemple, pour le tableau T suivant :

4	1	1	3
2	0	2	1
3	1	5	1

Un chemin est (0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3) (en gras sur le tableau) ;
La somme du chemin précédent est 14.
(0, 0), (0, 2), (2, 2), (2, 3) n’est pas un chemin.

L'objectif de cet exercice est de déterminer la somme maximale pour tous les chemins possibles allant de la case (0, 0) à la case (n – 1, p – 1).

Question 1

On considère tous les chemins allant de la case (0, 0) à la case (2, 3) du tableau T donné en exemple.

Un tel chemin comprend nécessairement 3 déplacements vers la droite. Combien de déplacements vers le bas comprend-il ?
La longueur d’un chemin est égal au nombre de cases de ce chemin. Justifier que tous les chemins allant de (0, 0) à (2, 3) ont une longueur égale à 6.

Question 2

En listant tous les chemins possibles allant de (0, 0) à (2, 3) du tableau T, déterminer un chemin qui permet d'obtenir la somme maximale et la valeur de cette somme.

Question 3

On veut créer le tableau T' où chaque élément T'[i][j] est la somme maximale pour tous les chemins possibles allant de (0, 0) à (i, j).

Compléter et recopier sur votre copie le tableau T' donné ci-dessous associé au tableau T précédent,
Justifier que si j est différent de 0, alors :
T'[0][j] = T[0][j] + T'[0][j-1]

Tableau T' à compléter :

4	5	6	?
6	?	8	10
9	10	?	16

Question 4

Justifier que si i et j sont différents de 0, alors :
T'[i][j] = T[i][j] + max(T'[i-1][j], T'[i][j-1]).

Question 5

Changement ici : on va utiliser la programmation dynamique au lieu de la récursivité. Le sujet évoque un tableau T' qui sert à l'explication mais n'est pas utilisé dans la version récursive. Nous devons maintenant créer ce tableau. Mais nous ne pouvons pas l'appeler T'… Nous l'appellerons T2.

Écrire une fonction somme_max(T) qui :

initialise T2 aux mêmes dimensions que T, rempli de 0,
initialise T2[0][0],
initialise la première ligne de T2,
initialise la première colonne de T2,
parcours les T2[i][j] pour 1 <= i < n et 1 <= j < p et les complète,
renvoie le contenu de T2[n-1][p-1].