CHAPITRE 3

Programmation dynamique

3.1 Introduction
La programmation dynamique, comme la méthode « diviser pour régner », résout les problèmes en
combinant les solutions de sous-problèmes. La programmation dynamique s’applique quand les sous-
problèmes ne sont pas indépendants mais ont des sous-sous-problèmes en commun. Dans ce cas, un
algorithme « diviser pour régner »fait plus de travail que nécessaire, en résolvant plusieurs fois les
sous-sous-problèmes communs. Un algorithme de programmation dynamique résout chaque sous-sous-
problème une unique fois et mémorise sa solution dans un tableau, s’épargnant ainsi le recalcul de
la solution chaque fois que le sous-sous-problème est rencontré. La programmation dynamique est en
général appliquée aux problèmes d’optimisation : ces problèmes peuvent admettre plusieurs solutions,
parmi lesquelles on veut choisir une solution optimale (maximale ou minimale pour une certaine fonction
de coût). Le développement d’un algorithme de programmation dynamique peut être planifié en quatre
étapes :
1. Caractériser la structure d’une solution optimale.
2. Définir récursivement la valeur d’une solution optimale.
3. Calculer la valeur d’une solution optimale partant des cas simples (cas d’arrêt des récursions) et
en remontant progressivement jusqu’aà l’énoncé du problème initial.
4. Construire une solution optimale pour les informations calculées (si l’on souhaite avoir une solu-
tion et pas seulement la valeur d’une solution optimale).

3.2 Multiplication d’une suite de matrices

On suppose que l’on a une suite de n matrices, A1 , . . . , An , et que l’on souhaite calculer le produit :

A1 A2 . . . An

On peut évaluer cette expression en utilisant comme sous-programme l’algorithme classique de mul-
tiplications de matrices, après avoir complètement parenthésé cette expression afin de lever toute ambi-

33
3.2 Multiplication d’une suite de matrices

guité sur l’ordre des multiplications de matrices - un produit de matrices complètement parenthésé est
soit une matrice unique soit le produit de deux produits de matrice complètement parenthésés).
La multiplication de matrices étant associative, le résultat de la multiplication est indépendant du
parenthésage. Il y a ainsi cinq manières différentes de calculer le produit de quatre matrices :

A1 A2 A3 A4 = (A1 (A2 (A3 A4 )))

= (A1 ((A2 A3 )A4 ))
= ((A1 (A2 A3 ))A4 )
= (((A1 A2 )A3 )A4 ))

Le parenthésage du produit peut avoir un impact crucial sur le coût de l’évaluation du produit. Le
produit d’une matrice A de taille p ⇥ q par une matrice B de taille q ⇥ r produit une matrice C de taille
p ⇥ r en pqr multiplications scalaires.
Considèrons trois matrices A1 , A2 et A3 de dimensions respectives 10 ⇥ 100, 100 ⇥ 5 et 5 ⇥ 50.
Si on effectue la multiplication de ces trois matrices suivant le parenthèsage ((A1 A2 )A3 , on effec-
tue 10 ⇥ 100 ⇥ 5 = 5000 multiplications dans un premier temps, puis 10 ⇥ 5 ⇥ 50 = 2500 dans un
deuxième temps, soit 7500 au total. Si, au contraire, on effectue la multiplication suivant le paren-
thèsage (A1 (A2 A3 )) on effectue 100 ⇥ 5 ⇥ 50 = 25000 multiplications dans un premier temps, puis
10 ⇥ 100 ⇥ 50 = 50000 dans un deuxième temps, soit 75000 au total et 10 fois plus qu’avec le premier
parenthèsage !

Problèmatique

Problèmatique de la multiplication d’une suite de matrices : étant donnée une suite A1 , . . . , An de n

matrices, où pour i = 1, 2, . . . , n la matrice Ai est de dimensions pi 1 ⇥ pi , parenthéser complètement
le produit A1 A2 . . . An de façon à minimiser le nombre de multiplications scalaires.

Nombre de parenthèsages

Le passage en revue de tous les parenthèsages possibles ne donnera pas un algorithme efficace, c’est
pourquoi il faut avoir recours à une technique plus sophistiquèe.
Soit P (n) le nombre de parenthèsages possibles d’une séquence de n matrices. On peut couper une
séquence de n matrices entre la k e et la (k + 1)e , pour k prenant n’importe quelle valeur dans l’intervalle
[1, n 1], puis parenthéser les deux sous-séquences résultantes indépendamment.
D’où la récurrence : (
1 si n = 1
P (n) = Pn 1
k=1 P (k)P (n k) si n 2
On peut montrer que :
1 n 1 4n
P (n) = C2n 2 = ⌦ 3
n n2
Le nombre de solutions est donc au moins exponentiel en n et la méthode directe consistant à effectuer
une recherche exhaustive est donc une stratégie médiocre . . .

3.2.1 Structure d’un parenthésage optimal

La première étape du paradigme de la programmation dynamique consiste à caractériser la structure
d’une solution optimale.
Nous notons Ai..j la matrice résultant de l’évaluation du produit Ai Ai+1 ...Aj 1 Aj . Un parenthésage
optimal de A1 A2 ...An sépare le produit entre Ak et Ak+1 pour une certaine valeur k.

34
 Chapitre 3. Programmation dynamique

Dans notre solution optimale on commence donc par calculer les matrices A1..k et Ak+1..n puis on
les multiplie pour obtenir la matrice A1..n recherchée. Le coût du calcul est donc la somme des coûts
des calculs des matrices A1..k et Ak+1..n et de leur produit.
Par conséquent le parenthésage de la sous-suite A1 ...Ak (et celui de la sous-suite Ak+1 ..An ) doit être
optimal : sinon, on le remplace par un parenthésage plus économique, et on obtient un parenthésage
global plus efficace.
Par conséquent, une solution optimale à une instance du problème de multiplication d’une suite de
matrices utilise uniquement des solutions optimales aux instances des sous-problèmes. La sous-structure
optimale à l’intérieur d’une solution optimale est l’une des garanties de l’applicabilité de la programma-
tion dynamique.

3.2.2 Résolution récursive

La deuxième étape du paradigme de la programmation dynamique consiste à définir récursivement
la valeur d’une solution optimale en fonction de solutions optimales aux sous-problèmes.
Pour le problème de la multiplication d’une suite de matrices, on prend comme sous-problèmes les
problèmes consistant à déterminer le coût minimum d’un parenthésage de Ai Ai+1 ...Aj , pour 1  i <
j  n.
Soit m(i, j) le nombre minimum de multiplications scalaires nécessaires au calcul de Ai Ai+1 ...Aj =
Ai..j .
Pour tout i, m(i, i) = 0 car Ai..i = Ai et aucune multiplication n’est nécessaire.
Considérons un couple (i, j) avec i < j. Supposons qu’un parenthésage optimal sépare le produit
Ai Ai+1 . . . Aj entre Ak et Ak+1 . Alors, m(i, j), le coût du calcul de Ai..j est égal au coût du calcul de
Ai..k , plus celui de Ak+1..j , plus celui du produit de ces deux matrices. Nous avons donc :

m(i, j) = m(i, k) + m(k + 1, j) + pi 1 p k pj .

Cette équation nécessite la connaissance de la valeur de k, connaissance que nous n’avons pas. Il
nous faut donc passer en revue tous les cas possibles et il y en a j i :
(
0 si i = j
m(i, j) = (3.1)
minik<j {m(i, k) + m(k + 1, j) + pi 1 pk pj } si i < j.

m(i, j) nous donne le coût d’une solution optimale. Pour pouvoir construire une telle solution on
note s[i, j] une valeur k telle que m(i, j) = m(i, k) + m(k + 1, j) + pi 1 pk pj .

Algorithme récursif

Une première solution à notre problème pourrait être l’algorithme

CHAÎNEDEMATRICES-RÉCURSIF ci-dessous qui est une utilisation directe de la récursion 3.1

CHAÎNEDEMATRICES-RECURSIF(p, i, j)
si i = j alors retourner 0
sinon
m +1
pour k i a j 1 faire
q CHAÎNEDEMATRICES-RECURSIF(p, i, k)

35
3.2 Multiplication d’une suite de matrices

+CHAÎNEDEMATRICES-RECURSIF(p, k + 1, j)
+ pi 1 pk p j
si q < m alors m q
s[i, j] k
finsi
finpour
finsi
retourner m

La complexié de cet algorithme est donné par la récurrence :

(
1 si n = 1
T (n) = Pn 1
k=1 (T (k) + T (n k) + 1) pour n 2
Dans le cas général, cette complexité peut se récrire :
n
X1
T (n) = 2 T (i) + n
i=1

Par conséquent T (n) 2T (n 1) et T (n) = ⌦(2n ). La quantité totale de travail effectué par l’appel
CHAÎNEDEMATRICES-RÉCURSIF(P, 1, n) est donc au moins exponentiel et est donc prohibitif. . .

3.2.3 Calcul des coûts optimaux

En fait, le nombre de sous-problèmes est assez réduit : un problème pour chaque choix de i et de
j tels que 1  i  j  n, soit au total Cn2 + n = ⇥(n2 ) choix. L’algorithme récursif rencontre chaque
sous-problème un grand nombre de fois (ici, un nombre exponentiel de fois) dans différentes branches
de l’arbre des appels récursifs.
Cette propriété, dite des sous-problèmes superposés (des sous-problèmes ont des sous-sous-problèmes
en commun), est le deuxième indice de l’applicabilité de la programmation dynamique.
Plutôt que d’implémenter de manière récursive l’équation 3.1, on aborde la troisième étape du para-
digme de la programmation dynamique : on calcule le coût optimal en utilisant une approche ascendante.
L’entrée de l’algorithme ORDONNER-CHAÎNEDEMATRICES ci-dessous est la séquence p0 , p1 , . . . , pn des
dimensions des matrices. Cet algorithme calcul le coût optimal m[i, j] et enregistre un indice s[i, j]
permettant de l’obtenir.

ORDONNER-CHAÎNEDEMATRICES(p)
n longueur(p) 1
pour i 1 a n faire
m[i, i] 0 // initialisation de la diagonle principale
finpour
pour l 2 a n faire
pour i 1 a n l + 1 faire
j i+l 1

36
 Chapitre 3. Programmation dynamique

m[i, j] +1
pour k i a j 1 faire
q m[i, k] + m[k + 1, j] + pi 1 pk pj
si q < m[i, j] alors m[i, j] q
s[i, j] k
finsi
finpour
finpour
finpour
renvoyer m, s

L’algorithme remplit le tableau m en considérant des suites de matrices de longueur croissante.

L’équation 3.1 nous montre en effet que le calcul du coût d’un produit de m matrices ne dépend que
des coûts de calcul de suites de matrices de longueur strictement inférieure.
La boucle sur l est une boucle sur la longueur des suites considérées. La figure 3.1 présente un
exemple d’exécution de l’algorithme ORDONNER-CHAÎNEDEMATRICES. Comme m[i, j] n’est défini que pour
i  j, seule la partie du tableau m strictement supérieure à la diagonale principale est utilisée.
Les deux tableaux sont présentés de manière à faire apparaître la diagonale principale de m horizon-
talement, chaque rangée horizontale contenant les éléments correspondants à des chaînes de matrices de
même taille.
ORDONNER-CHAÎNEDEMATRICES calcule les rangées de m du bas vers le haut, et chaque rangée de
la gauche vers la droite. Dans notre exemple, un parenthésage optimal coûte 15 125 multiplications
scalaires.

Figure 3.1 – Tableaux m et s calculés par ORDONNER-CHAÎNEDEMATRICES pour n = 6 et les dimensions :

30, 35, 15, 5, 10, 20, 25.

37
3.3 Éléments de programmation dynamique

3.2.4 Complexité
Un simple coup d’œil à l’algorithme montre que sa complexité est en O(n3 ). Plus précisément :
Pn Pn l+1 Pi+l 2
T (n) = 1
Pl=2 i=1
n Pn l+1
k=i
= (l 1)
Pl=2
n
i=1
= (n l + 1)(l 1)
Pl=2
n 2
= l=2 ( l + l(n + 2) (n + 1))
n3 +5n+12
= 6
Pn
sachant que i=1 i3 = n(n+1)(2n+1)
6 . La complexité de l’algorithme ORDONNER-CHAÎNEDEMATRICES est
donc en ⇥(n3 ) ce qui est infiniment meilleur que la solution naîve énumérant tous les parenthésages ou
que la solution récursive, toutes deux de complexité exponentielle.

3.2.5 Construction d’une solution optimale

L’algorithme ORDONNER-CHAÎNEDEMATRICES calcule le coût d’un parenthésage optimal, mais n’effec-
tue pas la multiplication de la suite de matrices.
Par contre, l’information nécessaire à la réalisation d’un calcul suivant un parenthésage optimal
est stockée au fur et à mesure dans le tableau s : s[i, j] contient une valeur k pour laquelle une
séparation du produit Ai Ai+1 . . . Aj entre Ak et Ak+1 fourni un parenthésage optimal. L’algorithme
MULTIPLIER-CHAÎNEDEMATRICES ci-dessous réalise la multiplication et résout donc notre problème.

MULTIPLIER-CHAÎNEDEMATRICES(A, s, i, j)
si (j > i) alors
X MULTIPLIER-CHAÎNEDEMATRICES(A, s, i, s[i, j])
Y MULTIPLIER-CHAÎNEDEMATRICES(A, s, s[i, j] + 1, j)
renvoyer MULTIPLIER-MATRICES(X, Y )
sinon renvoyer Ai
finsi

Dans l’exemple de la figure 3.1, MULTIPLIER-CHAÎNEDEMATRICES (A, s, 1, 6) calcule le produit de la

suite de matrices en suivant le parenthésage :

((A1 (A2 A3 ))((A4 A5 )A6 )),

car s[1, 6] = 3, s[1, 3] = 1 et s[4, 6] = 5.

3.3 Éléments de programmation dynamique

On examine ici les deux caractéristiques principales que doit posséder un problème d’optimisa-
tion pour que la programmation dynamique soit applicable : une sous-structure optimale et des sous-
problèmes superposés.
On examinera aussi une variante de ce paradigme : le recensement.

38
 Chapitre 3. Programmation dynamique

3.3.1 Sous-structure optimale

Un problème fait apparaître une sous-structure optimale si une solution optimale au problème fait
apparaître des solutions optimales aux sous-problèmes.
La présence d’une sous-structure optimale est un bon indice de l’utilité de la programmation dyna-
mique (mais cela peut aussi signifier qu’une stratégie gloutonne est applicable).
La sous-structure optimale d’un problème suggère souvent une classe de sous-problèmes pertinents
auxquels on peut appliquer la programmation dynamique.

3.3.2 Sous-problèmes superposés

La seconde caractéristique que doit posséder un problème d’optimisation pour que la programmation
dynamique soit applicable est « l’étroitesse »de l’espace des sous-problèmes, au sens où un algorithme
récursif doit résoudre constamment les mêmes sous-problèmes, plutôt que d’en engendrer toujours de
nouveaux.
En général, le nombre de sous-problèmes distincts est polynomial par rapport à la taille de l’entrée.
Quand un algorithme récursif repasse sur le même problème constamment, on dit que le problème
d’optimisation contient des sous-problèmes superposés. A contrario, un problème pour lequel l’approche
« diviser pour régner »est plus adaptée génère le plus souvent des problèmes nouveaux à chaque étape
de la récursivité.
Les algorithmes de programmation dynamique tirent parti de la superposition des sous-problèmes
en résolvant chaque sous-problème une unique fois, puis en conservant la solution dans un tableau où
on pourra la retrouver au besoin avec un temps de recherche constant.

3.4 Recensement
Il existe une variante de la programmation dynamique qui offre souvent la même efficacité que
l’approche usuelle, tout en conservant une stratégie descendante.
Son principe est de recenser les actions naturelles, mais inefficaces, de l’algorithme récursif.
Comme pour la programmation dynamique ordinaire, on conserve dans un tableau les solutions aux
sous-problèmes, mais la structure de remplissage du tableau est plus proche de l’algorithme récursif.
Un algorithme récursif de recensement maintient à jour un élément de tableau pour la solution de
chaque sous-problème.
Chaque élément contient au départ une valeur spéciale pour indiquer qu’il n’a pas encore été rempli.
Lorsque le sous-problème est rencontré pour la première fois durant l’exécution de l’algorithme
récursif, sa solution est calculée puis stockée dans le tableau.
À chaque nouvelle confrontation avec ce sous-problème, la valeur stockée est simplement récupérée.

RECENSEMENT-CHAÎNEDEMATRICES(p)
n longueur(p) 1
pour i 1 a n faire
pour j i a n faire
m[i, j] +1
finpour
finpour
renvoyer RECUPERATION-CHAÎNE(p, 1, n)

39
3.4 Recensement

RECUPERATION-CHAÎNE(p, i, j)
si m[i, j] < +1 alors renvoyer m[i, j]
sinon
si i = j alors m[i, j] 0
sinon
pour k i a j 1 faire
q RECUPERATION-CHAÎNE(p, i, k)
+ RECUPERATION-CHAÎNE(p, k + 1, j)
+pi 1 pk pj
si q < m[i, j] alors m[i, j] q
s[i, j] k
finsi
finpour
finsi
finsi

Chacun des ⇥(n2 ) éléments du tableau m est rempli une unique fois par RÉCUPÉRATION-CHAÎNE et
chacun de ces ⇥(n2 ) appels à RÉCUPÉRATION-CHAÎNE requiert un temps en O(n) en excluant le temps
passé à calculer d’autres éléments éventuels.
La complexité de RÉCUPÉRATION-CHAÎNE est donc en O(n3 ). En pratique, si tous les sous-problèmes
doivent être résolus au moins une fois, un algorithme ascendant de programmation dynamique bat
en général un algorithme descendant avec recensement d’un facteur constant car il élimine le temps
pris par les appels récursifs et prend moins de temps pour gérer le tableau. En revanche, si certains
sous-problèmes de l’espace des sous-problèmes n’ont pas besoin d’être résolus du tout, la solution du
recensement présente l’avantage de ne résoudre que ceux qui sont vraiment nécessaires.

40
 Chapitre 3. Programmation dynamique

3.5 Exercices
On définit sur les mots trois opérations élémentaires :
— la substitution : on remplace une lettre par une autre,
— l’insertion : on ajoute une nouvelle lettre,
— la suppression : on supprime une lettre.
Par exemple, sur le mot ’carie’, si on substitue c en d, a en u et si on insère t après le i, on obtient
’durite’.
La distance d’édition entre deux mots U et V est le nombre minimal d’opérations pour passer de U
à V . Ainsi, la distance de ’carie’ à ’durite’ est 3 : deux substitutions et une insertion. La distance de
’aluminuim’ à ’albumine’ est 4 : une insertion, b, une substitution, i en e et deux suppressions, u et m.
Posons
— i,j = 0 si la i-ème lettre de U et la j-ème lettre de V sont identiques, sinon 1 ;
— si U = u1 u2 u3 . . . un alors on appelle suffixe Ui = u1 u2 u3 . . . ui ;
— si V = u1 u2 u3 . . . um alors on appelle suffixe Vj = u1 u2 u3 . . . uj ;
— par convention U0 = V0 = ' , le mot vide.
Une formule de récurrence pour calculer la distance d’édition est
a. d(', Vj ) = j (j insertions) (la distance pour passer du mot vide ' au suffixe Vj ) ;
b. d(Ui , ') = i (i suppressions) (la distance pour passer du suffixe Ui au mot vide ') ;
c. d(Ui , Vj ) = min(d(Ui 1 , Vj 1 ) + i,j ; d(Ui 1 , Vj ) + 1; d(Ui , Vj 1 ) + 1) pour i 2 {1, 2, . . . , n}, j 2
{1, 2, . . . , m}.
1. Justifier cette formule de récurrence.
Indication : pour (c.), on écrit Ui et Vj sous la forme Ui = Ui 1 ↵ et Vj = Vj 1 et on considère
les différentes manières de transformer Ui en Vj ( il y a trois manières).
2. Écrire une fonction récursive Distance qui calcule la distance d’édition de deux chaînes de ca-
ractères de tailles respectives n et m. Testez-la sur ’carie’ et ’durite’, ’aluminui’ et ’albumine’.
3. Calculer la complexité de votre algorithme Distance.
Indication : On pourra raisonner sur deux mots de mêmes longueurs n. Remarquez que dans cet
algorithme les mêmes calculs sont faits plusieurs fois
Le problème de la fonction Distance est qu’elle effectue de nombreux appels récursifs redondants. Cela
conduit à une complexité exponentielle. La solution est de stocker les appels récursifs dans une table
D de dimension 2, telle que D(i, j) soit la distance de Ui à Vj . On ajoute une colonne et une ligne
pour traiter le mot vide '. Cela donne finalement une table indexée par 0 à n et 0 à m. Le résultat est
D(n, m). Par exemple, en supposant que les chaînes de caractères sont indexées à partir de 1, la table
pour ’carie’ et ’durite’ est

' d u r i t e
' 0 1 2 3 4 5 6
c 1 1 2 3 4 5 6
a 2 2 2 3 4 5 6
r 3 3 3 2 3 4 5
i 4 4 4 3 2 3 4
e 5 5 5 4 3 3 3

4. Écrire une fonction Distance_dynamique qui calcule la distance de deux chaînes de caractères
sans appels récursifs, en construisant la table D tout en justifiant l’utilisation du paradigme de

41
3.5 Exercices

la programmation dynamique.
5. Calculer la complexité de votre algorithme Distance_dynamique.
On veut maintenant connaitre la suite d’opérations qui mène de U à V . Pour cela, on peut visualiser
les transformations par un petit schéma :

c a r i - e a l - u m i n i u m
| | | | | | | | |
d u r i t e a l b u m i n e - -

Deux lettres identiques sont signalées par ’|’. Un espace dans le mot de départ correspond à une
insertion, un espace dans le mot d’arrivée correspond à une suppression, et une substitution est repré-
sentée par les deux lettres face à face, sans ’|’. Il est possible de connaître la dernière opération appliquée
en regardant comment la valeur de D(n, m) a été obtenue, et en remontant vers le début(case D(0, 0)).
On a :
d(i, j) = min(D(i 1, j 1) + i,j ; D(i 1, j) + 1; D(i, j 1) + 1)
— si D(i, j) = D(i, j 1) + 1 : insertion ;
— si D(i, j) = D(i 1, j) + 1 : suppression ;
— si D(i, j) = D(i 1, j 1) + i,j : substitution ou identité.
6. Retrouvez à la main à partir de la table de l’exemple la suite des transformations pour passer de
’carie’ à ’durite’.
7. (Facultative) Écrire une procédure récursive qui prend arguments deux chaînes de caractères et
affiche la suite d’opérations sous la forme décrite ci-dessus.
Pour cela, vous devez utiliser la table D et construire l’historique des transformations en remon-
tant dans la table à partir de la case D(n, m) jusqu’à la case D(0, 0).

42