</>

Programmation dynamique

Avancé

Mémoïsation, tabulation et les grands patterns de DP : ne plus jamais recalculer un sous-problème.

  1. 01

    Programmation dynamique : l'idée

    Si une récursion recalcule les mêmes sous-problèmes, on mémorise leurs résultats : un temps exponentiel devient polynomial.

  2. 02

    Tabulation : rendre la monnaie

    Le plus petit nombre de pièces pour former un montant : l'exemple type d'une DP en tableau à une dimension.

  3. 03

    Les patterns de DP à connaître

    Presque tous les problèmes de DP d'entretien sont une variante d'une poignée de formes.