la programmation dynamique 

La programmation dynamique est principalement une optimisation par rapport à la récursivité simple . Partout où nous voyons une solution récursive qui a des appels répétés pour les mêmes entrées, nous pouvons l'optimiser en utilisant la programmation dynamique. L'idée est de stocker simplement les résultats des sous-problèmes, de sorte que nous n'ayons pas à les recalculer en cas de besoin plus tard. Cette optimisation simple réduit les complexités temporelles d'exponentielle à polynomiale.

Par exemple, si nous écrivons une solution récursive simple pour les nombres de fibonacci, nous obtenons une complexité temporelle exponentielle et si nous l'optimisons en stockant des solutions de sous-problèmes, la complexité temporelle se réduit à linéaire.

Propriété des sous-problèmes superposés en programmation dynamique : 

La programmation dynamique est un paradigme algorithmique qui résout un problème complexe donné en le divisant en sous-problèmes à l'aide de la récursivité et en stockant les résultats des sous-problèmes pour éviter de recalculer les mêmes résultats. Voici les deux principales propriétés d'un problème qui suggèrent que le problème donné peut être résolu à l'aide de la programmation dynamique.

Dans cet article, nous discuterons en détail de la première propriété (sous-problèmes de chevauchement). 
1) Sous- problèmes superposés 
2) Sous- structure optimale

1) Sous-problèmes qui se chevauchent : 
Comme Divide and Conquer, la programmation dynamique combine des solutions aux sous-problèmes. La programmation dynamique est principalement utilisée lorsque des solutions aux mêmes sous-problèmes sont nécessaires encore et encore. En programmation dynamique, les solutions calculées aux sous-problèmes sont stockées dans une table afin qu'elles n'aient pas à être recalculées. La programmation dynamique n'est donc pas utile lorsqu'il n'y a pas de sous-problèmes communs (chevauchement) car il est inutile de stocker les solutions si elles ne sont plus nécessaires. Par exemple, la recherche binaire n'a pas de sous-problèmes communs. Si nous prenons l'exemple de suivre un programme récursif pour les nombres de Fibonacci, il existe de nombreux sous-problèmes qui sont résolus encore et encore.

13

Complexité temporelle : O(2^n), Comme à chaque étape, nous devons effectuer 2 appels.
Espace auxiliaire : O(1), car un espace supplémentaire constant est utilisé.

Arbre de récursivité pour l'exécution de fib(5) 

Nous pouvons voir que la fonction fib(3) est appelée 2 fois. Si nous avions stocké la valeur de fib(3), alors au lieu de la recalculer, nous aurions pu réutiliser l'ancienne valeur stockée. Il existe deux manières différentes de stocker les valeurs afin que ces valeurs puissent être réutilisées : 
a) Mémoïsation (Top Down) 
b) Tabulation (Bottom Up)

a) Mémoïsation (Top Down) : Le programme mémoïsé pour un problème est similaire à la version récursive avec une petite modification qui examine une table de recherche avant de calculer les solutions. Nous initialisons un tableau de recherche avec toutes les valeurs initiales comme NIL. Chaque fois que nous avons besoin de la solution à un sous-problème, nous regardons d'abord dans la table de recherche. Si la valeur précalculée est là, nous renvoyons cette valeur, sinon, nous calculons la valeur et mettons le résultat dans la table de recherche afin qu'il puisse être réutilisé plus tard.

Voici la version mémorisée du nième nombre de Fibonacci. 

    printf("Fibonacci number is %d ", fib);

Production

Le nombre de Fibonacci est 102334155

b) Tabulation (ascendante) : le programme tabulé pour un problème donné construit une table de manière ascendante et renvoie la dernière entrée de la table. Par exemple, pour un même nombre de Fibonacci, on calcule d'abord fib(0) puis fib(1) puis fib(2) puis fib(3), et ainsi de suite. Donc, littéralement, nous construisons les solutions aux sous-problèmes de bas en haut. 

Voici la version tabulée du nième nombre de Fibonacci.

int fib(int n)

{

    int f[n + 1];

    int i;

    f[0] = 0;

    f[1] = 1;

    for (i = 2; i <= n; i++)

        f[i] = f[i - 1] + f[i - 2];

 

    return f[n];

}

 

int main()

{

    int n = 9;

    printf("Fibonacci number is %d ", fib);

    return 0;

}

Production

Le nombre de Fibonacci est 34

Complexité temporelle : O, car nous traversons linéairement.
Espace auxiliaire : O, l'espace supplémentaire est utilisé dans le tableau de tabulation

Tabulé et mémorisé stockent les solutions aux sous-problèmes. Dans la version mémorisée, le tableau est rempli à la demande tandis que dans la version tabulée, à partir de la première entrée, toutes les entrées sont remplies une par une. Contrairement à la version tabulée, toutes les entrées de la table de recherche ne sont pas nécessairement renseignées dans la version mémoïsée. Par exemple, las solution mémorisée au problème LCS ne remplit pas nécessairement toutes les entrées.

Pour voir l'optimisation obtenue par les solutions mémoïsées et tabulées par rapport à la solution récursive de base, voyez le temps pris par les exécutions suivantes pour calculer le 40e nombre de Fibonacci :
Le temps pris par la méthode de récursivité est bien supérieur aux deux méthodes de programmation dynamique techniques mentionnées ci-dessus – Mémoïsation et tabulation !

Voir également la méthode 2 du post Ugly number pour un autre exemple simple où nous avons des sous-problèmes qui se chevauchent et nous stockons les résultats des sous-problèmes.