Programowanie dynamiczne, odnosząc się do dziedziny informatyki, opisuje grupę podobnych algorytmów komputerowych przeznaczonych do rozwiązywania złożonych problemów poprzez rozbicie problemu na zestawy mniejszych problemów. Po raz pierwszy stworzone przez Richarda Bellmana w latach 1950. programowanie dynamiczne działa z problemami, które są albo nakładającymi się podproblemami, albo optymalnymi podstrukturami. Aby zrozumieć, jak działa programowanie dynamiczne, najlepiej jest zrozumieć koncepcję stojącą za tymi dwoma terminami.
Zachodzące na siebie podproblemy opisują skomplikowane równania, które podzielone na mniejsze zestawy równań, ponownie wykorzystują części mniejszych równań więcej niż raz, aby uzyskać odpowiedź. Na przykład równanie matematyczne, które mówi, aby obliczyć wszystkie możliwe wyniki za pomocą zestawu liczb, może obliczyć ten sam wynik wiele razy, podczas gdy inne wyniki oblicza się tylko raz. Programowanie dynamiczne podpowiadałoby temu problemowi, że po pierwszym obliczeniu wyniku powinno go zapisać i później wstawić odpowiedź do równania, zamiast obliczać go ponownie. W przypadku długich złożonych procesów i równań oszczędza to czas i tworzy szybsze rozwiązanie przy znacznie mniejszej liczbie kroków.
Optymalne podstruktury tworzą rozwiązanie, znajdując najlepszą odpowiedź na wszystkie podproblemy, a następnie tworząc najlepszą odpowiedź ogólną. Po rozbiciu złożonego problemu na mniejsze problemy, komputer następnie używa systemu matematycznego do określenia najlepszej odpowiedzi dla każdego problemu. Oblicza odpowiedź na pierwotny problem z mniejszych odpowiedzi. W tym procesie istnieją wady. Chociaż daje rozwiązanie, które działa najlepiej matematycznie, może, ale nie musi, być najlepszym rozwiązaniem w prawdziwym życiu, w zależności od rodzaju problemu i jego związku z rzeczywistym światem.
Podczas każdej z tych operacji algorytm programowania dynamicznego próbuje znaleźć najkrótszą drogę do rozwiązania. Może to wymagać jednego z dwóch podejść. Podejście odgórne dzieli równanie na mniejsze równania i w razie potrzeby ponownie wykorzystuje odpowiedzi dla tych równań. Podejście oddolne próbuje rozwiązać najmniejszą wartość matematyczną po rozbiciu równania, a następnie kieruje się w górę w kierunku największej stamtąd. Oba podejścia oszczędzają czas, ale programowanie dynamiczne działa tylko wtedy, gdy pierwotny problem może rozpaść się na mniejsze równania, które w pewnym momencie są ponownie wykorzystywane do rozwiązania równania.