Recherche en Bioinformatique - Programmation dynamique
Prenons l'exemple de la suite de Fibonacci de manière à montrer comment l'utilisation d'un tableau de valeurs qui stocke les calculs intermédiaires permet d'améliorer l'efficacité d'un algorithme.

La suite de Fibonacci est donnée par la formule récurrente :
Pour calculer Fib(n) on peut utiliser un algorithme récursif :

Algorithme 1
Fonction Fib1(n : entier) : entier
debut
  si n <= 1 alors retour n;
  retour Fib1(n-1) + Fib1(n-2);
fin
Algorithme récursif pour le calcul de la suite de Fibonacci

Cet algorithme n'est pas efficace car il effectue les mêmes calculs de manière répétitive :
Sur cet exemple on voit que pour calculer Fib(6), il faut calculer Fib(5) puis Fib(4). Or, lors du calcul de Fib(5) on évalue déjà Fib(4).
On calculera donc 2 fois Fib(4).
Exemple de calcul pour Fibonacci de 6  

Pour améliorer l'efficacité du calcul on peut envisager une solution qui enregistre dans un tableau les valeurs de Fib(n) une fois calculées. Ce tableau est initialisé à 0. Une valeur tab[i] à 0 signifie que Fib(i) n'a pas encore été calculée :

Algorithme 2
Fonction Fib2(n : entier) : entier
debut
  si n = 0 alors retour 0;
  si tab[n] != 0 alors retour tab[n];
  tab[n] = Fib1(n-1) + Fib1(n-2);
  retour tab[n];
fin
Algorithme récursif pour le calcul de la suite de Fibonacci
avec stockage des valeurs intermédiaires dans un tableau

Enfin une dernière amélioration peut être apportée à l'algorithme précédent en remarquant qu'il suffit d'évaluer Fib(n) dans l'ordre croissant des n :

Algorithme 3
Fonction Fib3(n : entier) : entier
debut
  tab[0] = 0;
  tab[1] = 1;
  pour i = 2 à n faire
    tab[i] = tab[i-1] + tab[i-2];
  fpour
  retour tab[n];
fin
Algorithme pour le calcul de la suite de Fibonacci
avec calcul progressif

L'implantation en langage C des algorithmes et leur exécution sur machine nous permet d'obtenir le tableau de résultats suivants :

n Fib1 Fib2 ou 3
10 1s < 1s <
20 1s < 1s <
30 1s < 1s <
40 10s 1s <
50 20m 1s <
60 42h27m 1s <
Temps d'exécution sur serveur Helios

Ce tableau montre que l'algorithme Fib1 est de complexité exponentielle alors que Fib2 ou Fib 3 sont de compléxité linéaire.

Jean-Michel Richer, 2004