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
Longueur du plus long sous-chaîne sans caractères répétés
Étant donné une chaîne de caractères s, trouvez la longueur du plus long sous-chaîne sans caractères répétés.
Exemple 1:
<strong>Entrée:</strong> s = "abcabcbb"
<strong>Sortie:</strong> 3
<strong>Explication:</strong> Le plus long sous-chaîne sans caractères répétitifs est "abc", donc sa ...
Publié le 2 juillet à 22h00