Czym jest programowanie dynamiczne?

Programowanie dynamiczne (DP) to technika algorytmiczna służąca do rozwiązywania problemów optymalizacyjnych poprzez rozkładanie ich na prostsze podproblemy i ponowne wykorzystywanie rozwiązań tych podproblemów do rozwiązania pierwotnego problemu.

DP jest często stosowane w problemach, których rozwiązanie można wyrazić rekurencyjnie za pomocą mniejszych podproblemów. Technikę tę nazywa się „dynamiczną”, ponieważ rozwiązania podproblemów można zapisywać i ponownie wykorzystywać do rozwiązywania większych problemów, dzięki czemu proces jest wydajniejszy niż rozwiązywanie większego problemu od zera.

DP można stosować do różnych problemów, takich jak najkrótsza ścieżka, najdłuższy wspólny podciąg i maksymalna suma podtablicy. Jest szczególnie przydatne, gdy problem ma nakładające się podproblemy i optymalną podstrukturę, co oznacza, że optymalne rozwiązanie problemu można skonstruować z optymalnych rozwiązań jego podproblemów.