Une méthode pour résoudre des problèmes complexes en les décomposant en sous-problèmes qui se recoupent et en mémorisant leurs solutions (par mémoïsation ou tabulation), de sorte que chaque sous-problème n'est résolu qu'une seule fois et que les calculs redondants sont évités ; applicable lorsque le problème présente une structure optimale et des sous-problèmes recoupés.

Principe

S'appuyer sur le principe d'optimalité : une solution optimale à un problème contient des solutions optimales à ses sous-problèmes ; organiser le calcul autour d'une représentation d'état, d'une relation de récurrence et de la réutilisation des sous-résultats calculés.

Démonstration

Calculer le n-ième terme de la suite de Fibonacci en conservant les valeurs précédentes (mémoïsation ou table ascendante) : au lieu d'une récursion exponentielle, calculer F(0), F(1), …, F(n) une seule fois et les réutiliser. En optimisation, résoudre le sac à dos 0/1 en remplissant une table des meilleures valeurs pour chaque capacité et préfixe d'objets afin d'éviter de réévaluer les mêmes combinaisons.

Mauvaise application

Appliquer la programmation dynamique à des problèmes sans structure optimale (par exemple, où des choix locaux optimaux ne conduisent pas à un optimum global) ou à des problèmes dont l'espace d'états est extrêmement grand sans compression, entraînant des résultats incorrects ou une consommation de mémoire prohibitive.

Conséquence

Lorsque la méthode est applicable, des recherches naïves exponentielles peuvent souvent être réduites à des algorithmes en temps polynomial ; on échange du temps contre de l'espace (tables de mémoïsation), et les solutions sont reproductibles et exactes pour la représentation choisie.

Inversion

Approches gloutonnes ou diviser-pour-régner qui ne réutilisent pas les solutions de sous-problèmes et qui effectuent des choix locaux sans garantir l'optimalité globale ; elles peuvent être plus rapides mais erronées pour des problèmes demandant une coordination globale.

Limite

S'applique aux problèmes discrets avec états et récurrences bien définis ; exclut les problèmes dépourvus de structure optimale ou dont l'état ne peut pas être représenté de façon compacte (par exemple, certains problèmes non markoviens ou continus de haute dimension) et les cas où le compromis mémoire/temps est inacceptable.

Tension sémantique

Tension entre la mémoïsation (caching top-down) et la tabulation (itération bottom-up), et entre programmation dynamique et division classique : les deux décomposent les tâches mais diffèrent par la stratégie et l'ordre de réutilisation.

Synthèse

La programmation dynamique transforme systématiquement une récurrence ou une décomposition d'état en un calcul qui réutilise des sous-problèmes résolus, échangeant mémoire contre temps sous l'idée organisatrice que des solutions globales optimales proviennent de sous-solutions locales optimales ; son usage pratique requiert la conception d'états, de transitions et de limites de stockage.