Optimisation de la Programmation Dynamique par la Technique de l'Enveloppe Convexe
Modèle Mathématique et Interprétation Géométrique
La technique de l'enveloppe convexe (Convex Hull Trick) est une méthode d'optimisation puissante utilisée pour accélérer certaines récurrences de programmation dynamique. Elle s'applique typiquement aux équations de transition de la forme suivante :
\[ dp[i] = \min_{j < i} \{ dp[j] + A[i] + B ...
Publié le 3 septembre à 22h52