Optimisation de programmation dynamique avec le Baka's Trick
Considérons un problème classique de programmation dynamique (DP) dont la transition suit la forme suivante :
\[f(i) = \min_{i-k \le j < i} \{f(j) + \max(a_{j+1}, \dots, a_i)\}\]
L'objectif est d'optimiser cette transition pour passer d'une complexité naïve de \(O(n \cdot k)\) à une complexité linéaire ou quasi-linéaire.
Approche en \(O(n \l ...
Publié le 9 juillet à 04h56