La programmation dynamique est une méthode de résolution efficace de certains problèmes d'algorithmique, qui quand on en a compris le principe peut être très simple à mettre en oeuvre. Je vous propose ici d'en expliquer le fonctionnement, appuyé sur un exemple très explicite.
Le principe
Les algorithmes dynamiques sont une optimisation, visant à éviter de faire plusieurs fois le même calcul. Il s'agit simplement de stocker dans un tableau (de dimensions quelconques) les résultats de certains calculs, et de revenir les chercher au lieu de refaire le calcul. Cela peut sembler obscur au premier abord, mais cela apparait beaucoup plus facilement avec les fonctions récursives.En effet soit la fonction f(x,y) récursive, c'est à dire s'appelant elle même dans son corps, avec x et y variant entre 1 et 100. De combien de manières différentes cette fonction peut-elle être appelée ? Seulement 10000 ! Alors que la fonction peut être exécutée 2^100 fois par exemple pour certains problèmes. Il suffit alors de réaliser un tableaux de 100x100, initialisé à -1 par exemple, puis au tout début du corps de la fonction commencer par vérifier si le résultat a déjà été calculé, et dans le cas contraire faire le calcul et l'enregistrer dans le tableau.
Etudions tout de suite un exemple concret.
Un exemple : la suite de Fibonacci
La suite de Fibonacci est définie par :u0 = u1 = 1
un = un-1 + un-2
Ses premiers termes sont donc : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...
L'implémentation d'une fonction retournant le n-ième terme de la suite de Fibonacci est simple et efficace en itératif : il suffit de stocker les deux termes précédent et de les ajouter dans une boucle. Mais l'implémentation en récursif est plus intuitive car plus proche de la définition :
fibo(n) debut si (n = 0) ou (n = 1) alors rendre 1 sinon rendre fibo(n-1) + fibo(n-2) fin
Le problème de cette implémentation est évidemment sa complexité : dès que n devient un peu grand la fonction met un temps interminable à renvoyer le résultat. En effet, on voit facilement que la fonction s'appelle deux fois, et chaque appel donne lieu à deux autres appels jusqu'à arriver à n = 1. Le temps de calcul augmente donc exponentiellement avec n, plus précisément la complexité de l'algorithme serait de l'ordre de 2^n.
Or on constate que la fonction factorielle ne peut être appelée qu'avec n valeurs du paramètre, elle est donc appelée de nombreuses fois avec les mêmes valeurs.
La solution consiste donc à créer un tableau initialisé à -1 par exemple, et à modifier légèrement la fonction :
fibo(n) debut si tableau[n] = -1 alors debut si (n = 0) ou (n = 1) alors tableau[n] = 1 sinon tableau[n] = fibo(n-1) + fibo(n-2) fin rendre tableau[n]
fin
De cette manière la fonction est appelée au plus 2n fois, dont la moitié pour simplement renvoyer la valeur du tableau, puisque quand elle le fait elle épargne également de nombreux appels de fonctions. Sa complexité est donc en n, tout comme la version itérative.
Conclusion
Bien sûr cet exemple est un peu naïf car la solution itérative de complexité optimale est simple, mais exactement la même démarche fonctionne pour beaucoup de problèmes. Il suffit de résoudre le problème de façon récursive en explorant bêtement toutes les solutions, ce qui est le plus simple, puis repérer les variations des paramètres et modifier légèrement le code comme indiqué.Il est également possible d'utiliser la même technique en itératif (ce n'est pas parce que c'est itératif que c'est optimal), mais il faut un peu d'entraînement avant de pouvoir voir ce qu'il faut faire car il n'y a pas de recette qui fonctionne à tous les coups.
Le seul bémol de cette technique est évidemment l'occupation de la mémoire, et la nécessité d'avoir des paramètres bornés. Mais on peut dans de nombreux cas, comme il est possible de le faire avec la suite de Fibonacci, ne garder que quelques derniers termes, et dans les concours d'algorithmiques comme Prologin ou les Olympiades Internationales d'Informatique les paramètres sont de toute manière bornés.