Chapitre 16 : Programmation dynamique.

Introduction :

La programmation dynamique repose sur une idée simple mais puissante : pourquoi recalculer un résultat si on l'a déjà trouvé ?

En décomposant un problème complexe en sous-problèmes plus simples, on peut mémoriser les solutions déjà obtenues et les réutiliser. Cela permet d'éviter des calculs redondants et d'améliorer l'efficacité des algorithmes.

1. La programmation dynamique :

A copier dans le cahier.

La programmation dynamique est une méthode de conception d’algorithmes utilisée pour résoudre efficacement des problèmes complexes en les décomposant en sous-problèmes qui se répètent. Elle repose sur l’idée de mémoriser les résultats des sous-problèmes déjà résolus afin d’éviter de refaire plusieurs fois les mêmes calculs.

La programmation dynamique est souvent utilisée pour optimiser des calculs répétitifs, par exemple dans la suite de Fibonacci, les problèmes de plus court chemin (algorithme de Dijkstra), ou les problèmes de sac à dos (knapsack).

2. Etapes de la programmation dynamique :

Identification des sous-problèmes : le problème global peut être découpé en sous-problèmes plus petits et qui se recoupent.
Mémorisation : les solutions aux sous-problèmes sont stockées (dans un tableau ou un dictionnaire).
Réutilisation : lorsqu’un sous-problème réapparaît, on utilise directement la solution mémorisée.
Construction de la solution : la réponse finale est obtenue en combinant les solutions des sous-problèmes.

3. Activité : Suite de Fibonacci — itératif, récursif et dynamique

On considère la suite de Fibonacci définie à l'aide d'une suite \(F\) définie ainsi :

\(F(0)=0\)
\(F(1)=1\)
Pour tout \(n \ge 2\) : \(F(n)=F(n-1)+F(n-2)\)

Programmer la fonction fibo_itera(n) (version itérative).
Programmer la fonction fibo_recur(n) (version récursive simple).
Programmer la fonction fibo_recur_dyna(n) (récursif avec mémoïsation).
Programmer la fonction fibo_itera_dyna(n) (itératif avec tableau dynamique).

Exemples :

F(0)=0, F(1)=1, F(2)=1, F(5)=5, F(10)=55

def fibo_itera(n): """Version itérative: renvoie F(n).""" if n == 0: return ... if n == 1: return ... # on itère en gardant F(k-2) et F(k-1) a, b = 0, 1 for _ in range(...): # compléter la borne a, b = b, a + b return ... def fibo_recur(n): """Version récursive simple: renvoie F(n).""" if n == 0: return ... if n == 1: return ... return ... + ... def fibo_recur_dyna(n, memo=None): """Récursif + mémoïsation (dynamique top-down).""" if memo is None: memo = {} if n in memo: return memo[n] if n == 0: memo[0] = ... return ... if n == 1: memo[1] = ... return ... memo[n] = ... + ... # appels mémoïsés pour n-1 et n-2 return memo[n] def fibo_itera_dyna(n): """Itératif avec tableau (dynamique bottom-up).""" # construire une liste dp telle que dp[k] = F(k) dp = [0] * (... ) # longueur n+1 if n >= 1: dp[1] = 1 for k in range(2, ...): dp[k] = dp[k-1] + dp[k-2] return dp[...] n = 5 print(f"fibo_itera({n}) renvoie {fibo_itera(n)}.") print(f"fibo_recur({n}) renvoie {fibo_recur(n)}.") print(f"fibo_recur_dyna({n}) renvoie {fibo_recur_dyna(n)}.") print(f"fibo_itera_dyna({n}) renvoie {fibo_itera_dyna(n)}.")

Tests :

Affichage :

Console:

>>>

4. Exercice : Coût minimal dans une grille (programmation dynamique)

On dispose d’une grille rectangulaire de coûts (entiers positifs). On part de la case en haut à gauche et on veut atteindre la case en bas à droite.

À chaque étape, on peut se déplacer uniquement vers la droite ou vers le bas. Le coût d’un chemin est la somme des coûts des cases traversées (départ et arrivée inclus).

Objectif : écrire une fonction cout_chemin_min(grille, affiche_dp = False) qui renvoie le coût minimal pour aller du coin haut-gauche au coin bas-droit.

Idée (raisonnement dynamique) :

La case de départ « hérite » simplement de son propre coût.
Sur la première colonne, on ne peut venir que d’en haut : on additionne donc les coûts en descendant.
Sur la première ligne, on ne peut venir que de la gauche : on additionne donc les coûts en avançant.
Pour toute autre case, on arrive soit de la case du haut, soit de la case de gauche : on choisit le meilleur des deux chemins déjà calculés, puis on ajoute le coût de la case actuelle.

Exemples :

grille1 = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
# coût minimal attendu = 7

grille2 = [[5]]  # coût = 5

Un paramètre affiche_dp qui vaut par défaut False permettra de visualiser les deux grilles (matrices) si on le souhaite.

def cout_chemin_min(grille, affiche_dp = False): """ Renvoie le coût minimal pour aller de (0,0) à (n-1,m-1) en ne se déplaçant que vers la droite ou vers le bas. Paramètre: - grille : liste de listes d'entiers positifs (n x m, n>=1, m>=1) """ n = len(grille) m = len(grille[0]) # Table dp : dp[i][j] = coût minimal pour atteindre (i,j) dp = [[0 for _ in range(m)] for _ in range(n)] # Case de départ dp[0][0] = ... # coût de la case (0,0) # Première colonne : ne peut venir que d'en haut for i in range(1, n): dp[i][0] = ... # cumuler avec la case au-dessus # Première ligne : ne peut venir que de la gauche for j in range(1, m): dp[0][j] = ... # cumuler avec la case à gauche # Reste de la grille : meilleur des deux chemins (haut/gauche) + coût actuel for i in range(1, n): for j in range(1, m): dp[i][j] = ... if affiche_dp: print("Matrice initiale : grille") for ligne in grille: print(" ".join(f"{elem:3}" for elem in ligne)) print("") print("Matrice dp :") for ligne in dp: print(" ".join(f"{elem:3}" for elem in ligne)) print("") return ... # valeur en bas à droite # --- Grille de démonstration 6x6 (pour visualiser le résultat) --- grille_demo = [ [1, 3, 1, 2, 8, 2], [2, 1, 4, 1, 2, 3], [3, 2, 1, 5, 1, 4], [4, 3, 2, 1, 3, 1], [5, 1, 1, 1, 1, 2], [2, 2, 2, 2, 2, 1], ] print(cout_chemin_min(grille_demo, True))

Tests :

Affichage :

Console:

>>>

5. Exercice : Nombre de chemins dans une grille avec obstacles (programmation dynamique)

On modélise un plateau par une grille de 0 et 1 :

0 : case libre (on peut la traverser)
1 : obstacle (on ne peut pas la traverser)

On part du coin haut-gauche de la grille et on veut atteindre le coin bas-droit.

À chaque étape on peut se déplacer uniquement vers la droite ou vers le bas.

Objectif : écrire une fonction nombre_chemins(grille, affiche_dp=False) qui renvoie le nombre de chemins possibles de la case de départ à la case d’arrivée, en évitant les obstacles.

Idée (raisonnement dynamique) :

Si une case est un obstacle, le nombre de chemins jusqu’à cette case est 0.
La case de départ vaut 1 s’il n’y a pas d’obstacle dessus.
Sur la première ligne : on ne peut venir que de gauche (et seulement si toutes les cases précédentes sont libres).
Sur la première colonne : on ne peut venir que d’en haut (et seulement si toutes les cases au-dessus sont libres).
Ailleurs : le nombre de chemins pour atteindre une case libre est la somme des chemins venant de la case du haut et de la case de gauche.

Exemples :

grilleA = [
  [0, 0, 0],
  [0, 0, 0]
]
# 2 lignes, 3 colonnes, pas d'obstacle → il n'existe qu'un seul chemin par la première ligne
# puis tout droit vers le bas, OU bien tout droit en bas puis à droite → ici le résultat est 3.

grilleB = [
  [0, 1],
  [0, 0]
]
# Un obstacle en (0,1) (première ligne, deuxième colonne) bloque un des chemins.

Le paramètre affiche_dp permettra, s’il vaut True, d’afficher la grille et la matrice des nombres de chemins calculée.

def nombre_chemins(grille, affiche_dp=False): """ Renvoie le nombre de chemins du coin (0,0) au coin (n-1,m-1) en ne se déplaçant que vers la droite ou vers le bas, en évitant les obstacles (1). Paramètre: - grille : liste de listes d'entiers 0/1 (0=libre, 1=obstacle), taille n x m (n>=1, m>=1) - affiche_dp : si True, affiche la grille et la matrice DP """ n = len(grille) m = len(grille[0]) # Matrice DP : dp[i][j] = nb de chemins pour atteindre (i,j) dp = [[0 for _ in range(m)] for _ in range(n)] # Case de départ if grille[0][0] == 0: # 1 chemin possible de la case départ à la case départ dp[0][0] = 1 else: return 0 # aucun chemin possible # Première colonne : ne peut venir que d'en haut (si pas d'obstacle) for i in range(1, n): if grille[i][0] == 1: dp[i][0] = ... else: dp[i][0] = ... # si au-dessus 0, ça propage 0, sinon 1 # Première ligne : ne peut venir que de la gauche (si pas d'obstacle) for j in range(1, m): if grille[0][j] == 1: dp[0][j] = ... else: dp[0][j] = ... # Reste de la grille : somme (haut + gauche) si la case est libre for i in range(1, n): for j in range(1, m): if grille[i][j] == 1: dp[i][j] = ... else: dp[i][j] = ... if affiche_dp: print("Grille (0=libre, 1=obstacle) :") for ligne in grille: print(" ".join(str(x) for x in ligne)) print("") print("Matrice dp (nombre de chemins jusqu à la case) :") for ligne in dp: print(" ".join(f"{x:3}" for x in ligne)) print("") return ... # --- Grille de démonstration 6x6 (pour visualiser le résultat) --- # 0 = libre, 1 = obstacle grille_demo = [ [0,0,0,0,0,0], [0,1,0,0,1,0], [0,0,0,1,0,0], [1,0,0,0,0,0], [0,0,1,0,1,0], [0,0,0,0,0,0], ] print(nombre_chemins(grille_demo, True))

Tests :

Affichage :

Console:

>>>

6. Exercice : Sac à dos 0/1 (programmation dynamique)

Vous préparez un sac de randonnée. Chaque objet possède un poids (combien il pèse) et une valeur (son utilité/intérêt). Le sac a une capacité maximale : la somme des poids des objets choisis ne doit pas dépasser cette capacité. Chaque objet peut être pris au plus une fois.

Votre sac a une capacité maximale capacite (même unité que les poids). Vous ne pouvez pas dépasser cette capacité et vous ne pouvez prendre chaque objet au plus une fois (problème du sac à dos 0/1).

Objectif : écrire une fonction valeur_max_sac(liste_poids, liste_valeurs, capacite, affiche_dp=False) qui renvoie la valeur totale maximale transportable sans dépasser la capacité.

liste_poids[i] : le poids de l’objet i (par exemple en kg ou en centaines de grammes).
liste_valeurs[i] : l’utilité (ou score) de l’objet i. Plus la valeur est grande, plus l’objet est intéressant à emporter.

Idée de l'algorithme en programmation dynamique:

On raisonne par états : pour chaque nombre d’objets considérés (de 0 à n) et pour chaque capacité intermédiaire (de 0 à capacite), on mémorise la meilleure valeur atteignable.
Tableau de décision : chaque case répond à la question « en utilisant seulement les i premiers objets et en se limitant à une capacité w, quelle valeur maximale peut-on obtenir ? ».
Transition :
- Si l’objet courant est trop lourd pour w, on ne peut pas l’ajouter : la meilleure valeur reste celle obtenue sans cet objet.
- Sinon, on compare deux choix :
  - ne pas prendre l’objet → la valeur reste celle du meilleur choix précédent à capacité w ;
  - prendre l’objet → on ajoute sa valeur à la meilleure valeur obtenue avec la capacité w – poids_objet en ne considérant que les objets précédents.
  On retient le meilleur des deux choix.
Initialisation : avec 0 objet ou capacité 0, la meilleure valeur est 0.
Résultat : la case finale de la table correspond à « tous les objets considérés » et « capacité maximale » ; c’est la valeur optimale recherchée.
Affichage (optionnel) : si affiche_dp=True, afficher la table pour visualiser la construction de la solution.

def valeur_max_sac(liste_poids, liste_valeurs, capacite, affiche_dp=False): """ Renvoie la valeur maximale transportable sans dépasser 'capacite'. - liste_poids : liste d'entiers (poids des objets) - liste_valeurs : liste d'entiers (utilités/valeurs des objets, même ordre que 'poids') - capacite : entier (capacité maximale du sac) - affiche_dp : si True, affiche la table DP (lignes = objets 0..n, colonnes = 0..capacite) """ assert len(liste_poids) == len(liste_valeurs), "les deux listes doivent être de même taille" n = len(liste_poids) # dp[i][capacite_testee] : valeur max en utilisant les i premiers objets avec une capacité capacite_testee dp = [[0 for _ in range(capacite + 1)] for _ in range(n + 1)] for i in range(1, n + 1): i_eme_poids = liste_poids[i - 1] # poids de l'objet i (indexé i-1) i_eme_valeur = liste_valeurs[i - 1] # valeur de l'objet i for capacite_testee in range(0, capacite + 1): if i_eme_poids > capacite_testee: dp[i][capacite_testee] = ... # trop lourd : on ne prend pas else: dp[i][capacite_testee] = ... if affiche_dp: print("Table DP (lignes = objets 0..n, colonnes = capacités 0..C) :") for ligne in dp: print(" ".join(f"{v:3}" for v in ligne)) print("") return ... # --- Démo (optionnelle) --- poids_demo = [2, 3, 4, 5, 9, 7] valeurs_demo = [3, 4, 5, 8, 10, 9] cap_demo = 12 print(valeur_max_sac(poids_demo, valeurs_demo, cap_demo, True))

Tests :

Affichage :

Console:

>>>