2e année Informatique

Programmation dynamique
I Le type dictionnaire
I.1 Définition
Lorsque l’on manipule une liste en Python, on accède à ses éléments à l’aides d’indices, qui doivent
être des entiers naturels (consécutifs à partir de 0). Si l’on souhaite s’affranchir de cette contrainte, on
peut utiliser un autre type de données appelé dictionnaire, qui généralise en quelque sorte la notion
de liste en remplaçant les indices par des clés. Les clés d’un dictionnaire peuvent être des nombres
quelconques (pas nécessairement entiers), mais aussi des chaînes de caractères, des tuples, etc.

Définition (Dictionnaire) Un dictionnaire (ou tableau associatif) est une collection non ordonnée
de paires (clé,valeur).

En Python, on peut définir une variable de type dictionnaire ( dict ) en définissant les couples
(clé,valeur) sous la forme {cle1 :valeur1, cle2 :valeur2, ...} comme le montre l’exemple ci-dessous :
>>> D = { ’nom ’ : ’ E u l e r ’ , ’ pr énom ’ : ’ Leonhard ’ , 1707 : ’ n a i s s a n c e ’ }
>>> t y p e (D)
< c l a s s ’ d i c t ’>
>>> D
{ ’nom ’ : ’ E u l e r ’ , 1707 : ’ n a i s s a n c e ’ , ’ pr énom ’ : ’ Leonhard ’ }

Remarque : Comme nous le voyons sur cet exemple, les éléments de ce dictionnaire ne sont pas
homogènes : certaines clés sont des chaînes de caractères, d’autres des nombres, et il pourrait en
être de même pour les valeurs. Par ailleurs, les couples (clé,valeur) ne sont pas ordonnés, et peuvent
apparaître dans un ordre quelconque.

Pour accéder à une valeur d’un dictionnaire, on spécifie la clé entre crochets (comme l’indice d’une
liste) :
>>> D[ ’ pr énom ’ ]
’ Leonhard ’
>>> D[ 1 7 0 7 ]
’ naissance ’

Comme pour une liste, tenter d’accéder à un élément non défini provoquera une erreur (Keyerror pour
le type dict ).

>>> D[ ’ a d r e s s e ’ ]
Traceback ( most r e c e n t c a l l l a s t ) :
F i l e "<s t d i n >" , l i n e 1 , i n <module>
KeyError : ’ a d r e s s e ’

Remarque : Les clés d’un dictionnaire doivent être distinctes et de type immuable (nous reviendrons
un peu plus tard sur cette contrainte). En revanche, il n’y a pas de contrainte sur les valeurs, qui peuvent
être égales pour certaines, et de type mutable.

Programmation dynamique 1/15

2e année Informatique

I.2 Manipulation des dictionnaires

I.2.1 Définition incrémentale

Nous avons vu comment définir un dictionnaire directement par {cle1 :valeur1, cle2 :valeur2, ...} . On
peut également compléter un dictionnaire existant, en rajoutant des couples (clé,valeur) avec une
syntaxe de type D[cle]=valeur. Complétons ainsi l’exemple précédent :
>>> D[ ’ sp é c i a l i t é ’ ] = ’ math é m a t i q u e s ’
>>> D
{ ’ sp é c i a l i t é ’ : ’ math é m a t i q u e s ’ , ’nom ’ : ’ E u l e r ’ , 1707 : ’ n a i s s a n c e ’ , ’ pr énom ’ : ’ Leonhard ’ }

On aurait ainsi pu définir le dictionnaire précédent en partant d’un dictionnaire vide (que l’on peut
créer par un appel à la fonction dict , sans argument, ou bien avec la syntaxe {}) et en le complétant :
>>> D = {} # ou D = d i c t ( )
>>> D[ ’nom ’ ] = ’ E u l e r ’
>>> D[ ’ pr énom ’ ] = ’ Leonhard ’
>>> D[ 1 7 0 7 ] = ’ n a i s s a n c e ’
>>> D[ ’ sp é c i a l i t é ’ ] = ’ math é m a t i q u e s ’

I.2.2 Existence d’une clé

Afin d’éviter l’erreur KeyError, il est utile de pouvoir vérifier si une clé donnée existe dans un
dictionnaire avant de tenter d’accéder à la valeur correspondante. Ceci se fait simplement grâce à
l’instruction in :
>>> ’nom ’ i n D
True
>>> ’ a d r e s s e ’ i n D
False
>>> 1707 i n D
True
>>> ’ 1707 ’ i n D
False

On voit ici que la clé 1707 (de type int ) est bien distincte de la clé ’1707’ (de type str ) : la première est
une clé de D, la deuxième ne l’est pas.

I.2.3 Parcours d’un dictionnaire

Il est souvent utile de parcourir toutes les clés (ou tous les couples (clé,valeur)) d’un dictionnaire.
La méthode la plus courante pour cela est de parcourir les clés avec les instructions for et in :
>>> f o r c i n D :
... p r i n t ( " c l é : " , c , " / v a l e u r : " , D[ c ] )
...
c l é : sp é c i a l i t é / v a l e u r : math é m a t i q u e s
c l é : nom / v a l e u r : E u l e r
c l é : 1707 / v a l e u r : n a i s s a n c e
c l é : pr énom / v a l e u r : Leonhard

La liste des clés du dictionnaire D peut aussi s’obtenir directement avec D.keys() (attention à ne pas
oublier les parenthèses : keys est une méthode de D qui renvoie la liste de ses clés).
>>> D. k e y s ( )
d i c t _ k e y s ( [ ’ sp é c i a l i t é ’ , ’nom ’ , 1 7 0 7 , ’ pr énom ’ ] )

On remarque au passage que D.keys() ne renvoie pas un objet de type list , mais d’un type spécifique
dict_keys. Si l’on a besoin d’un objet de type list , la conversion peut se faire avec la fonction list :

Programmation dynamique 2/15

2e année Informatique

>>> l i s t (D. k e y s ( ) )
[ ’ sp é c i a l i t é ’ , ’nom ’ , 1 7 0 7 , ’ pr énom ’ ]

Pour parcourir les clés du dictionnaire D, on peut ainsi utiliser la syntaxe for c in D.keys() :, ou bien
la syntaxe (équivalente mais plus concise) for c in D :, qui lui est souvent préférée.
On peut également obtenir tous les couples (clé,valeur) du dictionnaire D avec la méthode items :
>>> D. i t e m s ( )
d i c t _ i t e m s ( [ ( ’ sp é c i a l i t é ’ , ’ math é m a t i q u e s ’ ) , ( ’nom ’ , ’ E u l e r ’ ) , ( 1 7 0 7 , ’ n a i s s a n c e ’ ) ,
( ’ pr énom ’ , ’ Leonhard ’ ) ] )

Là encore, on pourra utiliser éventuellement la fonction list pour convertir le type spécifique dict_items

en type list . L’affichage du contenu de D, réalisé plus haut, peut ainsi se réécrire sous la forme
équivalente
>>> f o r c , v i n D. i t e m s ( ) :
... p r i n t ( " c l é :" , c , " / valeur :" , v )
...
c l é : sp é c i a l i t é / v a l e u r : math é m a t i q u e s
c l é : nom / v a l e u r : E u l e r
c l é : 1707 / v a l e u r : n a i s s a n c e
c l é : pr énom / v a l e u r : Leonhard

Notons enfin l’existence de la méthode values, qui permet d’obtenir la liste des valeurs (avec répé-
titions éventuelles) associées aux clés d’un dictionnaire :
>>> D. v a l u e s ( )
d i c t _ v a l u e s ( [ ’ E u l e r ’ , ’ Leonhard ’ , ’ n a i s s a n c e ’ , ’ math é m a t i q u e s ’ ] )

I.2.4 Autres fonctions liées aux dictionnaires

La fonction len et la méthode copy, qui s’appliquent déjà aux listes, ont le même comportement sur
un objet de type dictionnaire. Ainsi, len(D) retourne le nombre de couples (clé,valeur) du dictionnaire
D, et D.copy() retourne une copie du dictionnaire D.

Remarque : Comme pour le type list , la méthode copy ne fait pas une copie récursive des valeurs
du dictionnaire. Comme nous l’avons vu en révision sur les listes, il faudra donc ici encore utiliser
la fonction deepcopy du module copy pour obtenir une copie complète (indépendante) d’un dictionnaire
ayant des valeurs de type list .

I.3 Les clés d’un dictionnaire doivent être hachables

Le langage Python impose une restriction sur les clés d’un dictionnaire : certains types de données
ne sont pas autorisés. Il n’est par exemple pas possible d’utiliser le type list :
>>> D = { [ 1 4 9 5 , 1 5 9 8 ] : ’ r e n a i s s a n c e ’ }
Traceback ( most r e c e n t c a l l l a s t ) :
F i l e "<s t d i n >" , l i n e 1 , i n <module>
TypeError : u n h a s h a b l e t y p e : ’ l i s t ’

mais il est en revanche possible d’utiliser le type tuple :

>>> D = { ( 1 4 9 5 , 1 5 9 8 ) : ’ r e n a i s s a n c e ’ }
>>> D
{(1495 , 1598) : ’ r e n a i s s a n c e ’ }

Pourquoi cette limitation à certains types autorisés ? Pour que la manipulation d’un dictionnaire
soit efficace, il faut pouvoir accéder rapidement à la valeur associée à une clé. Lors de l’évaluation de

Programmation dynamique 3/15

2e année Informatique

D[c], Python ne fait pas un parcours systématique de toutes les clés du dictionnaire D jusqu’à trouver
celle correspondant à la valeur de c. Une telle méthode, de complexité Θ(n) (où n est le nombre de
clés du dictionnaire), fonctionnerait correctement pour un dictionnaire de petite taille, mais serait
beaucoup trop lente pour un dictionnaire de plusieurs millions ou milliards d’éléments !
Pour retrouver rapidement la valeur associée à une clé d’un dictionnaire, Python utilise une fonction
de hachage, hash. Cette fonction associe à un objet Python de type hachable un entier de type int :
>>> hash ( 1 4 9 5 ) # pour un e n t i e r a s s e z p e t i t , hash e s t l a f o n c t i o n i d e n t i t é
1495
>>> hash ( [ 1 4 9 5 , 1 5 9 8 ] ) # i n c o r r e c t ( l e t y p e l i s t n ’ e s t pas h a c h a b l e )
TypeError : u n h a s h a b l e t y p e : ’ l i s t ’
>>> hash ( ( 1 4 9 5 , 1 5 9 8 ) ) # c o r r e c t ( l e t y p e t u p l e e s t h a c h a b l e )
3712308706137777606
>>> hash ( ’ Python 3 ’ ) # l a f o n c t i o n hash e s t a u s s i d é f i n i e pour d e s cha î n e s
1842537825426745422
>>> hash ( 3 . 1 4 1 5 ) # ou d e s f l o t t a n t s
326276785803738115
>>> hash ( 1 0 ∗ ∗ 2 0 ) , hash ( 8 4 8 7 5 0 6 0 3 8 1 1 1 6 0 1 0 7 ) # l a f o n c t i o n hash n ’ e s t pas i n j e c t i v e
(848750603811160107 , 848750603811160107)

Les types hachables que nous serons amenés à manipuler sont :

— les types simples ( int , float , bool, str , ...)
— les tuples formés d’éléments de type eux-mêmes hachables.
Plus généralement, les types hachables sont les types non mutables (on dit aussi immuable, ou im-
mutable) dont tous les constituants (pour les types composés) sont également hachables (donc en
particulier immuables). Ainsi, une liste n’est pas hachable (car mutable), mais un tuple formé d’en-
tiers est hachable. De même, un tuple contenant une liste n’est pas hachable, mais un tuple contenant
des tuples formés de types simples est hachable.
L’intérêt d’une fonction de hachage est qu’elle permet de répartir les clés dans des « paquets »dé-
finis à partir de la valeur de hachage, de sorte que la recherche d’une clé puisse ensuite se faire en
temps constant (c’est-à-dire avec une complexité Θ(1), indépendante de la taille du dictionnaire). La
contrepartie pour cette efficacité est que les clés d’un dictionnaire doivent être hachables.

Remarque : Il n’y a en revanche aucune contrainte sur les valeurs d’un dictionnaire, qui peuvent
être de type quelconque : type simple, liste, tuple, et même dictionnaire ! Nous aurons l’occasion de
rencontrer de tels exemples dans la suite.

II Mémoïsation
Une application très utile du type dictionnaire est la mémoïsation d’une fonction.

Définition (Mémoïsation) La mémoïsation d’une fonction consiste à mettre en place (en général
à l’aide d’un dictionnaire) un système qui mémorise les arguments d’entrée (clé) et le résultat de la
fonction (valeur) lors de chaque appel de la fonction, et évite ainsi de refaire un même calcul lorsque
la fonction est appelée plusieurs fois avec les mêmes arguments.

Comme nous allons le voir, la mémoïsation est particulièrement efficace pour les fonctions récur-
sives.
Considérons la suite de Fibonacci (Fn )n∈N définie par F0 = 0, F1 = 1 et la relation de récurrence

∀n ≥ 2, Fn = Fn−1 + Fn−2 .

Programmation dynamique 4/15

2e année Informatique

Implémentons le calcul de Fn à l’aide d’une fonction récursive naïve :

def fib ( n : int ) -> int :
’’’ renvoie le terme d ’ indice n de la suite de Fibonacci ( calcul
doublement r é cursif )
’’’
if n <= 1:
return n
return fib (n -1) + fib (n -2)

Avec cette implémentation, l’exécution de fib (50) prend plus d’une heure ! La raison est simple :
l’appel fib (50) provoque un appel à fib (49) et fib (48), mais fib (49) produit de son côté un appel indépendant
à fib (48) et fib (47), de sorte que fib (48) est calculé 2 fois. Et la situation empire pour les arguments
inférieurs : fib (47) est appelé 3 fois, fib (46) 5 fois, . . . et fib (1) est appelé plus de 12 milliards de fois !
Évidemment, l’implémentation que nous avons choisie est particulièrement inefficace, à cause du
double appel récursif, et on pourrait facilement éviter cet écueil en utilisant une fonction non récursive.
Mais comme nous allons le voir, on peut également conserver l’idée initiale d’une fonction récursive,
et ajouter simplement une étape de mémoïsation pour éviter les recalculs inutiles.
Dfib = {} # dictionnaire pour la m é mo ï sation de la fonction fib

def fib ( n : int ) -> int :

’’’ renvoie le terme d ’ indice n de la suite de Fibonacci
( calcul doublement r é cursif avec m é mo ï sation via le dictionnaire Dfib )
’’’
if n <= 1:
return n
if n not in Dfib :
Dfib [ n ] = fib (n -1) + fib (n -2)
return Dfib [ n ]

Avec cette implémentation, l’évaluation de fib (50) est instantanée. Le principe de la mémoïsation

apparaît clairement sur cet exemple : on associe à la fonction fib un dictionnaire Dfib qui va stocker les
valeurs déjà calculées de la fonction. Lors de l’appel fib (n), on commence par examiner si n est une clé
de ce dictionnaire Dfib. Si ce n’est pas le cas, on calcule la valeur de la fonction pour cet argument n et
on complète le dictionnaire. La valeur à retourner par la fonction est alors, dans les deux cas, Dfib[n] .

On notera au passage que dans la fonction fib , le premier test correspond à la condition d’arrêt de
la récursion (n = 0 ou n = 1). L’utilisation de l’instruction else après ce test n’est pas nécessaire en
raison de l’instruction return qui provoque la sortie de la fonction lorsque le test est vrai.
La mémoïsation permet de diminuer la complexité en temps d’un algorithme. Dans l’exemple pré-
√
1+ 5
cédent, on peut montrer que l’on passe d’une complexité Θ(φn ) à Θ(n), où φ = 2 est le nombre
d’or, ce qui est un gain considérable (on passe d’une complexité exponentielle à une complexité li-
néaire). Il faut cependant noter que ce gain de complexité temporelle se fait généralement au prix
d’une complexité en mémoire supérieure, en raison du stockage des valeurs calculées dans un dic-
tionnaire. Dans l’exemple précédent, cette complexité en mémoire est Θ(n) puisque le calcul de fib (n)

provoque le stockage de toutes les valeurs de fib (k) pour 2 ≤ k ≤ n.

Remarque : Rien n’empêche d’utiliser la mémoïsation pour une fonction à plusieurs paramètres,
tant que ceux-ci restent de type hachable. Les clés du dictionnaire de mémoïsation sont alors des
tuples qui rassemblent les paramètres de la fonction.

Programmation dynamique 5/15

2e année Informatique

III La programmation dynamique

La programmation dynamique est une technique d’optimisation inventée par Richard Bellman dans
les années 1950. Le terme programmation doit être ici entendu dans le sens général de planification,
et non dans le sens informatique (activité consistant à écrire un programme informatique). On peut
le rapprocher du terme programmation linéaire également utilisé en optimisation.
La programmation dynamique est une stratégie de programmation utilisée pour résoudre des pro-
blèmes en exploitant les solutions trouvées à des sous-problèmes. Ainsi, elle s’approche du paradigme
de résolution appelé ń diviser pour régner ż.
Plutôt que de décrire de manière théorique le principe de la programmation dynamique, ce qui
serait assez indigeste, nous allons considérer un exemple (tout de même assez général) qui nous servira
de référence par la suite.

III.1 Exemple modèle

III.1.1 Description du problème

On considère un problème de vente de barre de métal. Le problème est de déterminer la coupe de

barre permettant d’obtenir le maximum d’argent. On suppose que la barre fait une longueur n mètres
et que la découpe peut se faire sur des longueurs entières uniquement.
Le tableau suivant donne la liste des prix p(i) d’une découpe donnée i.

ℓ 1 2 3 5 7 11 ... i
p 1 5 6 12 12 13 ... p(i)
Si on se fixe un longueur n = 10, on peut regarder différentes découpes et chercher celle qui donne
le gain le plus important.
Par exemple : p(5)+p(5) = 24 (découpe de la barre en 2), p(2)+p(3)+p(5) = 23, p(1)+p(2)+p(7) =
18 et p(2) + p(2) + p(2) + p(2) + p(2) = 25.

Pour la suite, on définit la fonction p(i ) qui renvoie le prix d’une découpe à la longueur i selon le
tableau défini précédemment.
def p ( i ) :
d ={1:1 ,2:5 ,3:6 ,4:7 ,5:12 ,6:12 ,7:12 ,8:12 ,
9:13 ,10:13 ,11:13 ,12:14 ,13:14 ,14:14 ,15:15}
return d [ i ]

III.1.2 Approche très naïve

On peut tester toutes les possibilités de découpe en cherchant les combinaisons pour un n donné.
Pour les dénombrer, on compte le nombre d’endroits de découpe possible : n − 1 et on décide si on
coupe ou non à chacun de ces n − 1 endroits.
Cela représente donc 2n−1 combinaisons.

Cela fait beaucoup de possibilités et si n est élevée, cette recherche peut prendre du temps. Mais
on est sûr de trouver le résultat optimal !

Programmation dynamique 6/15

2e année Informatique

III.1.3 Approche gloutonne

Définition Un algorithme glouton (ou vorace) est une procédure algorithmique qui construit une
solution d’une manière incrémentale selon le principe de faire, étape par étape, un choix optimum
local, dans l’espoir d’obtenir un résultat optimum global.

Remarque : Ce choix, localement optimal, n’a aucune raison de conduire à une solution globalement
optimale. Cependant, certains problèmes peuvent être résolus d’une manière optimale ainsi. Dans
d’autres cas, la méthode gloutonne est seulement une heuristique qui ne conduit qu’à une solution
sous-optimale, mais qui peut être utilisée quand on ne connaît pas d’algorithme exact efficace.
Dans une méthode gloutonne, les choix ne sont jamais remis en cause : une fois faits, on ne revient
pas dessus.
Selon cette approche, on choisit une manière de sélectionner les découpes qui semble être optimale.
On n’est pas assuré de trouver la meilleure solution.
Par exemple, on pourrait dire ici que l’on ordonne les découpes selon l’ordre décroissant des rapports
prix/longueur et on cherche alors le nombre de coupes que l’on peut faire pour chaque découpe.
Ici, on aurait : découpes : 2, 5, 3, 7, 1... On trouverait alors 5 découpes de 2 soit un gain de 25.

III.1.4 Approche de type "diviser pour régner"

On fait l’hypothèse qu’on sait résoudre des problèmes de taille inférieure à n. On va donc découper
en 2 la barre et dire qu’on sait résoudre de manière optimale le problème pour chaque partie de la
barre.
On note M (n) le prix optimal pour une barre de longueur n. La difficulté est qu’on ne sait pas où
couper la barre. On note cette position i. Ainsi la partie de gauche possède un prix optimal M (i) et
la partie de droite M (n − i).
Le problème à{ résoudre est : }
M (n) = max max {M (i) + M (n − i)}, p(n)
1≤i≤n−1

(en effet, il se peut que la vente de la barre sans découpe soit la meilleure solution !)
Cette équation est appelée équation de Bellman.
Ce problème peut être écrit récursivement :
def decoupe ( n ) :
if n ==0:
return 0
else :
m =0
for i in range (1 , n ) :
res = decoupe ( i ) + decoupe (n - i )
if res > m :
m = res
return max (m , p ( n ) )

La récursivité va « appeler »la résolution des sous-problèmes qui découlent du problème initial.
Ceci va générer de nombreux appels récursifs redondants (la résolution d’un même sous-problème va
être sollicitée par l’examen de plusieurs solutions potentielles).
Étudions la complexité de cette fonction récursive en notant C(n) la complexité associée à une
itération n en termes de comparaisons.

Programmation dynamique 7/15

2e année Informatique

∑
n
Démonstration : On constate que C(0) = 0 et la partie récursive correspond à C(n) = 1+ (C(i)+
i=1
∑
n−1
C(n − i)). Par un changement de variable, on obtient C(n) = 1 + 2 C(i). En soustrayant C(n) −
i=1
C(n−1) on obtient : C(n)−C(n−1) = 2.C(n−1). Ainsi C(n) = 3C(n−1). On a C(n) = 3n−1 .C(1) =
3n−1 .
On constate ainsi que la complexité de la fonction est exponentielle.

III.1.5 Résolution par mémoïsation (de haut en bas - top-down)

Il est essentiel de réécrire la fonction récursive en utilisant la mémoïsation pour éviter les recal-
culs inutiles (sans cela, on perdrait tout le bénéfice de la programmation dynamique). On appelle
cette approche : l’approche « de haut en bas »(top-down en anglais), ou approche par mémoïsation.
L’algorithme associé s’écrit :
mem ={0:0}
def decoupe_memo (n , mem ) :
if n ==0:
return 0
else :
if n not in mem . keys () :
m=p(n)
for i in range (1 , n ) :
res = decoupe_memo (i , mem ) + decoupe_memo (n -i , mem )
if res > m :
m = res
mem [ n ]= m
return mem [ n ]
print ( decoupe_memo (10 , mem ) )

La complexité temporelle est en Θ(n2 ) ce qui est nettement mieux que la complexité exponentielle
de la fonction récursive basique. Cependant, il est nécessaire de stocker n valeurs supplémentaires dans
le dictionnaire mem (la complexité spatiale est en Θ(n).

III.1.6 Approche de programmation dynamique, de bas en haut (bottom-up)

Plutôt que de travailler par récursivité et de partir du résultat recherché pour un n donné et appeler
les valeurs pour des n inférieures, une autre technique consiste à procéder de manière incrémentale en
partant de M (0).
En effet, il suffit d’utiliser l’équation de Bellman et la condition limite pour calculer successivement
les termes nécessaires à une évaluation pour un n élevé.
Ainsi, pour déterminer M (1) il faut connaître M (0) uniquement. Pour déterminer M (2), il faut
connaître M (0) et M (1) qui ont déjà été calculés (et mémorisés). Pour déterminer M (3), il faut
connaître M (0) et M (2) ainsi que M (1). De la même manière en calculant successivement les valeurs
des M (i) en utilisant les valeurs déjà calculées, on peut évaluer facilement la solution optimale M (n)
avec un n quelconque.
Comme précédemment la complexité spatiale est en Θ(n) et la complexité temporelle en Θ(n2 ).
La fonction python correspondant à la résolution de ce problème s’obtient naturellement en utilisant
un dictionnaire et une double boucle.

Programmation dynamique 8/15

2e année Informatique

def decoupe_progdyn ( n ) :
C ={0:0}
for i in range (1 , n +1) :
maxi = p ( i )
for j in range (1 , i ) :
res = C [ j ]+ C [i - j ]
if maxi < res :
maxi = res
C [ i ]= maxi
return C [ n ]

print ( decoupe_progdyn (12) )

Remarque : On constate à travers cet algorithme qu’on aurait pu utiliser la symétrie de l’équation
de Bellman pour la simplifier car les calculs sont faits en double à chaque fois. Cela ne change pas la
complexité asymptotique du problème.

III.1.7 Calcul d’une solution optimale

L’algorithme que nous venons de décrire permet de calculer efficacement le coût optimal du pro-
blème de découpe (le prix maximal que l’on peut tirer de la découpe), mais il ne dit pas comment
découper.
Pour déterminer une solution optimale (c’est à dire un chemin correspondant à la découpe optimale
de la barre), il faut stocker en plus de la valeur de la fonction coût les indices de réalisation du
maximum. Ces indices correspondent à la découpe optimale en deux. En stockant les différentes valeurs
dans un dictionnaire pour chaque itération, on peut remonter de proche en proche aux lieux de découpe
optimale.
Cette technique de recherche du lieu de réalisation d’un maximum (ou un minimum) correspond à
la fonction argmax (ou argmin). Elle peut être mise en oeuvre sur la technique top-down ou bottom-
up.
On donne ci-dessous la modification de la fonction de type bottom-up pour récupérer les indices
des découpes.
def decoupe_progdyn ( n ) :
C ={0:0}
D ={0:[0 ,0]}
for i in range (1 , n +1) :
maxi = p ( i )
D [ i ]=[0 , i ]
for j in range (1 , i ) :
res = C [ j ]+ C [i - j ]
if maxi < res :
maxi = res
D [ i ]=[ j ,i - j ] # on d é coupe en une barre de longueur j
# et une de longueur i - j
C [ i ]= maxi
return C [ n ]

Il reste une dernière étape appelée rétropropagation qui consiste à :

Programmation dynamique 9/15

2e année Informatique

— partir de la longueur de barre recherchée

— déterminer en utilisant le dictionnaire D les 2 longueurs de barre optimales
— stocker la valeur la plus petite
— réutiliser le dictionnaire pour chercher la découpe optimale de la barre de longueur la plus
grande
— remonter ainsi jusqu’à atteindre une longueur de barre la plus grande nulle.
On ajoute ainsi le code suivant pour sortir en plus du coût optimal de découpe les longueurs
découpées réalisant le maximum.
def decoupe_progdyn ( n ) :
C ={0:0}
D ={0:[0]}
for i in range (1 , n +1) :
maxi = p ( i )
D [ i ]=[ i ]
for j in range (1 , i ) :
res = C [ j ]+ C [i - j ]
if maxi < res :
maxi = res
D [ i ]=[ j ,i - j ] # on d é coupe en une barre de longueur j
# et celle de longueur i - j
C [ i ]= maxi

decoupes =[]
dec = D [ n ]
while dec [0]!=0:
decoupes . append ( dec [0])
dec = D [ dec [1]]
decoupes . append ( dec [1])
return C [ n ] , decoupes

On constate ainsi que la fonction renvoie bien une découpe en 6 morceaux de 2 pour une longueur
initiale de valeur 12 (gain de 25), ou une découpe en 4 morceaux de longueurs 2 et un morceau de
longueur 5 pour une longueur initiale de valeur 13 (gain de 32).

III.2 Cas général

On peut remarquer deux propriétés essentielles du problème que nous venons de traiter :
1. les solutions du problème de départ possèdent une propriété de sous-structure optimale :
si un chemin E = (x0 , x1 , . . . , xN ) est solution, alors tout sous-chemin (xk , xk+1 , . . . , xℓ ) de E
est aussi un chemin optimal (i.e. de coût optimal) parmi tous les chemins allant de l’état xk à
l’état xℓ .
2. les sous-chemins à considérer pour résoudre le problème initial ne sont pas indépendants mais
entremêlés : il y a ce qu’on appelle un chevauchement des sous-problèmes.
Ces deux propriétés (sous-structure optimale et chevauchement de sous-problèmes) caractérisent les
problèmes que l’on peut résoudre par programmation dynamique. Si l’on a la propriété de sous-
structure optimale mais pas la propriété de chevauchement, alors on peut utiliser le principe diviser

Programmation dynamique 10/15

2e année Informatique

pour régner (comme par exemple dans l’algorithme du tri rapide), très efficace mais bien différent de
la programmation dynamique.
De manière générale, pour résoudre un problème par programmation dynamique, on peut procéder
comme suit :
1. on considère des sous-problèmes plus généraux que le problème initial (typiquement en faisant
varier un ou plusieurs paramètres du problème), et on définit des fonctions de coût associées ;
2. on détermine une équation de Bellman établissant une relation de récurrence (généralisée) entre
ces fonctions de coût ; si l’on n’y parvient pas, il faut probablement revoir la définition des
sous-problèmes, qui doivent partager la même structure et être interdépendants ;
3. on examine soigneusement les cas limites de la fonction de coût et de l’équation de Bellman, car
ils serviront de conditions d’arrêt pour la récursivité ;
4. on choisit entre une approche de bas en haut et une approche par mémoïsation ;
5. on écrit d’abord un algorithme (ou une fonction Python) permettant de calculer le coût optimal ;
6. on écrit ensuite, en complétant le travail de l’étape précédente, un algorithme (ou une fonction
Python) qui retourne une solution de coût optimal.
En ce qui concerne le choix d’une approche de bas en haut ou d’une approche par mémoïsation,
plusieurs considérations entrent en jeu :
— lorsque le problème initial est très homogène, et lorsque l’ordre des calculs est facile à trouver,
l’approche de bas en haut est un peu plus simple à écrire en général ;
— dans les autres cas, l’approche par mémoïsation est préférable.
Pour finir, on peut noter qu’il y a souvent plusieurs manières de décomposer un même problème
de départ en sous-problèmes. Il ne faut donc pas hésiter à considérer plusieurs possibilités avant de se
lancer dans une voie particulière.

III.3 Autre exemple : rendu de monnaie

III.3.1 Rappel du problème

Revenons sur le problème du rendu de monnaie, déjà abordé dans le cadre des algorithmes gloutons.
Soit S ∈ N la somme à former, et P = (pi )0≤i≤n−1 la famille des valeurs (strictement positives) des
pièces (avec des centimes d’euros, les valeurs sont 200, 100, 50, 20, 10, 5, 2, 1, mais nous considérons
ici le cas général). On rappelle que l’objectif est de former la somme S à l’aide des valeurs de P en
utilisant un minimum de pièces.
Si l’on note xi le nombre d’exemplaires choisi pour la pièce de valeur pi , le problème d’optimisation
à résoudre s’énonce ainsi : minimiser
∑
n−1
xi
i=0

∑
n−1
parmi toutes les familles (xi )0≤i≤n−1 ∈ Nn telles que S = p i xi .
i=0
Une méthode de type force brute comporte 2n combinaisons possibles (soit on utilise une pièce
soit on ne l’utilise pas).
Une implémentation de type glouton peut être testée.
P =[1 ,2 ,5 ,10 ,20 ,50 ,100 ,200]
P . sort ( reverse = True )

Programmation dynamique 11/15

2e année Informatique

def rendu_glouton (S , P ) :
Sr = S
res =[]
for p in P :
nb = Sr // p
if nb !=0:
Sr = Sr % p
res . append ( nb )
return res

Elle a l’avantage pour les pièces en euros de donner la solution optimale. Mais ce n’est pas toujours
le cas. L’idée fondamentale de cet algorithme est de trier par ordre décroissant les valeurs des pièces
puis parcourir ces pièces pour savoir si la somme peut être atteinte.

III.3.2 Sous-problèmes et équation de Bellman

Notons ck (s) la solution du sous-problème associé obtenu en n’utilisant que les pièces (pi )0≤i≤k−1
pour atteindre une somme entière s ≤ S. Autrement dit, ck (s) est le nombre minimal de pièces de
valeurs (p0 , . . . , pk−1 ) nécessaires pour former la somme s.
Avec cette définition, la solution du problème initial est cn (S), ce qui correspond aux choix k = n
(toutes les valeurs dans P sont acceptées) et s = S (somme totale à former).
On obtient l’équation de Bellman

ck (s) = min ck−1 (s − xpk−1 ) + x

x∈N
s−xpk−1 ≥0

en faisant l’observation suivante : si, pour former la somme s, on utilise x exemplaires de la pièce de
valeur pk−1 , alors il restera ensuite à former la somme s − xpk−1 à l’aide des valeurs (p0 , . . . , pk−2 ).
Notons au passage la contrainte s − xpk−1 ≥ 0 qui contraint les valeurs possibles de x.
Il faut compléter cette équation (valable pour k ≥ 1 et s > 0) par des conditions aux limites
(conditions d’arrêt de la récursion) correspondant aux valeurs connues de ck (s) :
— ck (0) = 0 pour tout k ≥ 1 (aucune pièce n’est nécessaire pour rendre une somme nulle) ;
— c0 (s) = +∞ pour tout s > 0 (pas de rendu possible si aucune pièce n’est disponible).
En pratique, nous utiliserons la valeur float("inf").

Au passage, on peut remarquer que si aucune pièce de valeur 1 n’est disponible, le problème initial
n’a pas toujours une solution (en particulier pour S = 1).

III.3.3 Calcul du coût minimal

s
On remarque que la condition s−xpk−1 ≥ 0 s’écrit x ≤ , puis, comme x est entier, x ≤ s//pk−1
pk−1
(avec la notation // empruntée à Python pour le quotient de la division euclidienne).
On obtient alors le programme récursif suivant qui renvoie le nombre minimum de pièces qu’il faut
pour former la somme S.
def c_rec ( k : int , s : int , pieces :[]) -> int :
if s ==0: return 0
elif k ==0: return float ( " inf " )

Programmation dynamique 12/15

2e année Informatique

else :
mini = float ( " inf " )
for x in range (1+ s // pieces [k -1]) :
c = c_rec (k -1 ,s - x * pieces [k -1] , pieces ) + x
if c < mini : mini = c
return mini
print ( c_rec ( len ( P ) ,123 , P ) ) # renvoie 4

Comme précédemment, cette implémentation a une complexité exponentielle et sur l’exemple in-
diqué, il faut un peu de temps pour sortir un résultat.
En introduisant un dictionnaire dont les clés sont les couples (k, s) pour mettre en place l’approche
par mémoïsation, on obtient le code suivant :
memo ={(0 ,0) :0}
def c_memo ( k : int , s : int , pieces :[]) -> int :
if s ==0: return 0
elif k ==0: return float ( " inf " )
else :
if (k , s ) not in memo :
mini = float ( " inf " )
for x in range (1+ s // pieces [k -1]) :
c = c_memo (k -1 ,s - x * pieces [k -1] , pieces ) + x
if c < mini : mini = c
memo [( k , s ) ]= mini
return memo [( k , s ) ]
print ( c_memo ( len ( P ) ,123 , P ) ) # renvoie 4

Cette implémentation est beaucoup plus rapide.

L’approche de type bottom-up consisterait à créer un tableau contenant les valeurs du nombre
minimum de pièces pour chaque couple (k, s).
def c_bottomup ( S : int , pieces :[]) -> int :
D ={(0 ,0) :0}
for k in range (1 , len ( pieces ) +1) :
D [( k ,0) ]=0
for s in range (1 , S +1) :
D [(0 , s ) ]= float ( " inf " )
if (k , s ) not in D :
mini = float ( " inf " )
for x in range (1+ s // pieces [k -1]) :
c = D [( k -1 ,s - x * pieces [k -1]) ] + x
if c < mini : mini = c
D [( k , s ) ]= mini
return D [( len ( pieces ) ,S ) ]

On observe plus facilement avec cette implémentation que la complexité est comprise entre Θ(nS)
et Θ(nS 2 ) avec n nombre de pièces.

III.3.4 Détermination d’une solution optimale

À partir de la fonction qui calcule le coût minimal (ici le nombre de pièces rendues), on déduit
naturellement la fonction qui retourne une solution optimale, en ajoutant :

Programmation dynamique 13/15

2e année Informatique

— le calcul des argmin, en plus des minimums (on utilise les fonctions de python min et index pour
avoir un code plus concis) ;
— une étape de rétro-propagation à partir de la dernière étape de calcul du coût minimal (à noter
que dans cette étape, il faut mettre à jour la somme à former) ;
— une étape supplémentaire permettant de construire la liste des pièces (liste sol ) à partir des
valeurs des (xi )0≤i≤n−1 .
d e f rendu_monnaie ( S : i n t , p i e c e s : l i s t ) −> l i s t :
’’’
S : somme à f o r m e r
p i e c e s : l i s t e des v a l e u r s des pi è ces
r e n v o i e une l i s t e de p i è c e s de t a i l l e minimale p e r m e t t a n t de f o r m e r l a somme S
( c a l c u l par programmation dynamique , a p p r o c h e par mémo ï s a t i o n )
’’’

d e f cX ( k , s ) : # co û t minimal e t argument ( p i è c e s d ’ i n d i c e s 0 à k −1 , somme s )

i f s==0 :
r e t u r n ( 0 , 0 ) # s o l u t i o n de co û t n u l
e l i f k==0 :
r e t u r n ( f l o a t ( " i n f " ) , None ) # s o l u t i o n i n c o r r e c t e ( c o n t r a i n t e non s a t i s f a i t e )
else :
i f ( k , s ) not i n DcX :
L = [ cX ( k −1 , s−x∗ p i e c e s [ k −1]) [ 0 ] + x f o r x i n r a n g e (1+ s // p i e c e s [ k −1]) ]
m=min (L)
DcX [ ( k , s ) ]=(m, L . i n d e x (m) )
r e t u r n DcX [ ( k , s ) ]

DcX = {} # d i c t i o n n a i r e pour l a mémo ï s a t i o n de cX

n = l e n ( p i e c e s ) # nombre de p i è c e s
x = [ 0 ] ∗ n # i n i t i a l i s a t i o n de l a s o l u t i o n
# c a l c u l de l a d e r n i è r e composante de l a s o l u t i o n
x [ n−1] = cX ( n , S ) [ 1 ]
# r é t r o −p r o p a g a t i o n
k = n−1
w h i l e k>=1 :
S −= p i e c e s [ k ] ∗ x [ k ]
x [ k −1] = cX ( k , S ) [ 1 ]
k −= 1
return x

On peut alors vérifier le bon fonctionnement de cette nouvelle fonction :

>>> rendu_monnaie ( 3 9 9 , [ 2 0 0 , 1 0 0 , 5 0 , 2 0 , 1 0 , 5 , 2 , 1 ] ) # c a s r é a l i s t e : r e n d r e 3 , 9 9 e u r o s
[1 , 1 , 1 , 2 , 0 , 1 , 1 , 2]
>>> rendu_monnaie ( 1 0 , [ 7 , 5 , 1 ] ) # c a s q u i met en d é f a u t l ’ a l g o r i t h m e g l o u t o n
[0 , 2 , 0]
>>> rendu_monnaie ( 1 0 0 , [ 5 8 , 2 2 , 7 , 5 , 1 ] ) # a u t r e exemple mal r é s o l u par l ’ a l g o r i t h m e g l o u t o n
[0 , 4 , 1 , 1 , 0]

IV Calcul récursif et programmation dynamique

Une confusion fréquente est faite entre la programmation dynamique et le calcul récursif. Même
chez certains informaticiens chevronnés, on voit parfois qualifié de « programmation dynamique »un
algorithme de calcul récursif qui n’a rien à voir avec un problème d’optimisation. Le terme « program-
mation dynamique », qui ne suggère pas nécessairement l’idée d’optimisation de prime abord, y est
certainement pour quelque chose.
Une autre raison probable à cette confusion est certainement la proximité des approches. Dans les
deux cas, on dispose d’une formulation récursive, et on peut choisir une résolution de bas en haut ou

Programmation dynamique 14/15

2e année Informatique

par mémoïsation. Le calcul du terme général de la suite de Fibonacci (Fn ), par exemple, peut être
effectué de bas en haut avec une simple boucle (à partir des valeurs initiales F0 et F1 , on applique la
relation de récurrence pour calculer successivement F2 , F3 , . . . , Fn ), ou bien par mémoïsation avec
une double récursivité (les valeurs initiales F0 et F1 servant alors de test d’arrêt).
La différence est qu’en programmation dynamique, on résout un problème d’optimisation, ce qui
conduit quasiment toujours à une étape de rétro-propagation (on est en général plus intéressé par la
construction d’un minimiseur que par la valeur du coût minimal), alors que dans le deuxième cas il
s’agit d’un calcul direct. En un sens, la programmation dynamique est donc une généralisation du
principe de calcul récursif.

Programmation dynamique 15/15