La programmation dynamique, en se référant au domaine de l'informatique, décrit un groupe 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 se chevauchaient sous-problèmes ou des sous-structures optimales. Pour comprendre comment fonctionne la programmation dynamique, il est préférable de comprendre le concept derrière ces deux termes.
Sous-problèmes qui se chevauchent décrivent équations complexes qui, lorsqu'ils sont ventilés en petits ensembles d'équations, de réutiliser une partie des petites équations à plusieurs reprises pour atteindre une réponse. Par exemple, une équation mathématique dit de calculer tous les résultats possibles en utilisant un ensemble de nombres peuvent calculer le même résultat de nombreuses reprises lors du calcul d'autres résultats qu'une seule fois. La programmation dynamique dirait que ce problème après avoir calculé le résultat de la première fois, il doit enregistrer ce résultat et branchez la réponse à l'équation plus tard au lieu de calculer à nouveau. Dans les processus et les équations longues et complexes, ce qui économise du temps et crée une solution plus rapide en utilisant beaucoup moins d'étapes.
Structures optimales créer une solution en trouvant la meilleure réponse à tous les sous-problèmes et puis 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 solution pour chaque problème. Il calcule la réponse au problème initial des petites réponses. 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.
Au cours de l'une de ces opérations, l'algorithme de programmation dynamique tente de trouver le chemin le plus court à 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 valeur mathématique plus petit après la rupture de l'équation vers le bas et ensuite fait son chemin vers le haut vers le plus grand à partir de là. Les deux approches gagner du temps, mais la programmation dynamique ne fonctionne que lorsque le problème d'origine peut se décomposer en petites équations qui à un moment donné sont réutilisés pour résoudre l'équation.