Programmation dynamique

La récursion simple recalcule les mêmes sous-problèmes plusieurs fois, ce qui entraîne une complexité souvent exponentielle. La programmation dynamique, elle, stocke le résultat de chaque sous-problème dans une mémoire (tableau ou dictionnaire) dès qu'il est calculé. Ainsi, chaque sous-problème n'est résolu qu'une seule fois.

💡 À retenir : La programmation dynamique transforme une complexité exponentielle en une complexité polynomiale grâce au stockage.

1. Chof wach l mochkil momkin n9smoh l machakil sghira (sous-problèmes).
2. Chof wach l7l dyal l mochkil l kbir kayt3temed 3la l7l dyal l machakil sghira (sous-structure optimale).
3. Chof wach l khwarizmiya katsm3 l nafs l mochkil bzaf d l mrat (chevauchement).

💡 À retenir : Ila ban lik l'algorithme récursif kay3awed nafs l7sab bzaf, rah programmation dynamique hiya l7l.

Oui, pour les problèmes présentant des sous-problèmes qui se chevauchent. Cependant, elle consomme plus de mémoire (espace) pour stocker les résultats intermédiaires. Si le problème ne présente pas de chevauchement, la programmation dynamique n'apporte aucun gain de performance.

💡 À retenir : C'est un compromis temps-mémoire (Time-Memory Trade-off).

1. Top-down (mémoïsation) : Kanbdaou mn l mochkil l kbir w kanst3mlo récursion, w fach kanl9aw l7l kanstokiwah.
2. Bottom-up (itérative) : Kanbdaou mn l7alat l basiya (cas de base) w kanbniw l7l 7ta kanwslou l l7l l kbir bla ma nst3mlo récursion.

💡 À retenir : Bottom-up katkon souvent plus rapide 7it mmafihach l'overhead dyal l'appel récursif.

La taille du tableau dépend du nombre d'états nécessaires pour définir chaque sous-problème. Si le problème dépend d'un paramètre $n$, on utilise généralement un tableau de taille $n+1$. S'il dépend de deux paramètres $n$ et $m$, on utilise une matrice de taille $(n+1) \times (m+1)$.

💡 À retenir : La dimension du tableau correspond au nombre de variables qui changent dans les appels récursifs.

Oui, par exemple pour trouver le plus court chemin dans un graphe acyclique orienté (DAG) ou pour l'algorithme de Floyd-Warshall qui calcule les plus courts chemins entre toutes les paires de sommets.

💡 À retenir : La programmation dynamique est un outil puissant pour optimiser les parcours dans les graphes.

La complexité spatiale correspond à la taille de la structure de données utilisée pour stocker les résultats (le tableau ou la matrice). Si tu utilises un tableau de taille $n$, la complexité est $O(n)$. Si tu utilises une matrice $n \times m$, elle est $O(n \times m)$.

💡 À retenir : Il faut toujours compter l'espace mémoire supplémentaire alloué pour la mémoïsation.

Oui, souvent. Si pour calculer l'état $i$, on n'a besoin que des états $i-1$ et $i-2$, on n'a pas besoin de stocker tout le tableau. On peut utiliser seulement deux ou trois variables pour garder les valeurs nécessaires.

💡 À retenir : C'est l'optimisation de l'espace, très utile quand $n$ est très grand.

Oui, elle fait partie intégrante du programme de 2ème année CPGE pour la filière TSI, dans le cadre de l'étude des algorithmes d'optimisation.

💡 À retenir : Maîtriser la transition entre récursion et programmation dynamique est un point clé pour le concours.

On l'appelle ascendante (bottom-up) parce qu'on résout d'abord les plus petits sous-problèmes (les bases), puis on utilise ces résultats pour construire la solution des problèmes de plus en plus grands, jusqu'à atteindre le problème initial.

💡 À retenir : On construit la solution brique par brique.

C'est une propriété où la solution optimale d'un problème global peut être construite à partir des solutions optimales de ses sous-problèmes. Par exemple, le plus court chemin entre A et C passant par B est la somme du plus court chemin A-B et du plus court chemin B-C.

💡 À retenir : Sans sous-structure optimale, la programmation dynamique ne fonctionne pas.

Non, les algorithmes de tri classiques (Tri fusion, Tri rapide) utilisent plutôt la méthode "Diviser pour régner". La programmation dynamique est spécifique aux problèmes d'optimisation avec chevauchement.

💡 À retenir : Ne pas confondre les paradigmes algorithmiques.