Hvad er dynamisk programmering?
Dynamisk programmering beskriver, når man henviser til området videnskab, en gruppe af lignende computeralgoritmer beregnet til at løse komplekse problemer ved at opdele problemet i sæt mindre problemer. Først oprettet af Richard Bellman i 1950'erne, fungerer dynamisk programmering med problemer, der enten overlapper underproblemer eller optimale substrukturer. For at forstå, hvordan dynamisk programmering fungerer, er det bedst at forstå konceptet bag disse to udtryk.
Overlappende delproblemer beskriver komplicerede ligninger, der, når de opdeles i mindre sæt ligninger, genbruger dele af de mindre ligninger mere end én gang for at nå et svar. For eksempel kan en matematisk ligning, der får besked om at beregne alle mulige resultater ved hjælp af et sæt tal, beregne det samme resultat adskillige gange, mens andre resultater kun beregnes én gang. Dynamisk programmering fortæller dette problem, at det efter beregning af resultatet første gang skulle gemme dette resultat og sætte svaret i ligningen senere i stedet for at beregne det igen. Når man håndterer lange komplekse processer og ligninger, sparer dette tid og skaber en hurtigere løsning ved hjælp af langt færre trin.
Optimale substrukturer skaber en løsning ved at finde det bedste svar på alle underproblemer og derefter oprette det bedste samlede svar. Efter at have opdelt et komplekst problem i mindre problemer, bruger computeren derefter et matematisk system til at bestemme, hvad det bedste svar til hvert problem er. Det beregner svaret på det originale problem ud fra de mindre svar. Der findes mangler ved denne proces. Selvom det giver den løsning, der fungerer bedst matematisk, er den måske eller måske ikke den bedste løsning i det virkelige liv, afhængigt af typen af problem og hvordan det forholder sig til den virkelige verden.
Under en af disse operationer forsøger den dynamiske programmeringsalgoritme at finde den korteste vej til løsningen. Det kan tage en af to tilgange til at gøre dette. Top-down-fremgangsmåden nedbryder ligningen i mindre ligninger og genbruger svarene for disse ligninger, når det er nødvendigt. Bund-up-fremgangsmåden forsøger at løse den mindste matematiske værdi efter nedbrydning af ligningen og derefter arbejder sig op mod den største derfra. Begge fremgangsmåder sparer tid, men dynamisk programmering fungerer kun, når det originale problem kan nedbrydes i mindre ligninger, der på et tidspunkt genbruges til at løse ligningen.