52. Introduction à la Dynamic Programming (DP - Programmation Dynamique)

La Dynamic Programming est une technique puissante principalement utilisée pour les problèmes d'optimisation. Elle évite les calculs redondants en stockant les résultats des sous-problèmes.

Quand la DP est-elle Applicable ?

La DP convient aux problèmes présentant deux propriétés clés :

1. Structure Optimale (Optimal Substructure) : Une solution optimale au problème peut être construite à partir de solutions optimales à ses sous-problèmes (similaire à Greedy/D&C).
2. Sous-problèmes Chevauchants (Overlapping Subproblems) : Les mêmes sous-problèmes sont résolus à plusieurs reprises par un algorithme récursif. C'est cette redondance que la DP cible.

DP vs. Divide and Conquer

• D&C : Les sous-problèmes sont indépendants (par exemple, trier le côté gauche du Merge Sort n'affecte pas le tri du côté droit).
• DP : Les sous-problèmes sont interdépendants et se chevauchent (par exemple, le calcul de Fibonacci(5) nécessite Fibonacci(4) et Fibonacci(3). Le calcul de Fibonacci(4) nécessite également Fibonacci(3)).