La programmation dynamique, en se référant au domaine de l'informatique, décrit un ensemble d'algorithmes informatiques similaires destinés à résoudre des problèmes complexes en décomposant le problème en séries de petits problèmes. D'abord créé par Richard Bellman dans les années 1950, la programmation dynamique fonctionne avec des problèmes qui sont soit sous-problèmes qui se chevauchent ou sous-structures optimales. Pour comprendre comment fonctionne la programmation dynamique, il est préférable de comprendre le concept derrière ces deux termes.
Les sous-problèmes qui se chevauchent décrivent équations complexes qui, une fois décomposés en plus petits ensembles d'équations, réutilise une partie de l’équation plus petite et plus d'une fois pour trouver une réponse. Par exemple, une équation mathématique dit de calculer tous les résultats possibles en utilisant un ensemble de nombres peut calculer le résultat même de nombreuses fois lors du calcul des résultats autres qu'une seule fois. La programmation dynamique dirais que ce problème après avoir calculé le résultat de la première fois, il doit sauver ce résultat et branchez la réponse dans l'équation plus tard au lieu de le calculer à nouveau. Lorsque vous traitez avec de longs processus complexes et des équations, ce qui économise du temps et crée une solution plus rapide en utilisant beaucoup moins d'étapes.
Les structures optimales de créer une solution de trouver la meilleure réponse à tous les sous-problèmes, puis de créer la meilleure réponse globale. Après décomposer un problème complexe en problèmes plus petits, l'ordinateur utilise alors un système mathématique pour déterminer quelle est la meilleure réponse pour chaque problème. Il calcule la réponse au problème initial à partir des réponses plus petites. Les failles existent dans ce processus. Bien qu'il donne la solution qui fonctionne le mieux mathématiquement, il peut ou peut ne pas être la meilleure solution dans la vraie vie, selon le type de problème et comment il se rapporte au monde réel.
Lors de ces opérations, l'algorithme de programmation dynamique essaie de trouver le plus court chemin vers la solution. Il peut prendre l'une des deux approches pour ce faire. L'approche top-down rompt l'équation en petites équations et réutilise les réponses à ces équations lorsque cela est nécessaire. L'approche bottom-up tente de résoudre la plus petite valeur mathématique après la rupture de l'équation vers le bas et travaille ensuite son chemin vers la plus grande place à partir de là. Les deux approches gagner du temps, mais la programmation dynamique fonctionne uniquement lorsque le problème initial peut décomposer en petits équations qui à un moment donné sont réutilisées pour résoudre l'équation.