Pomoću algoritama dinamičkog programiranja, potproblemi jednog problema postaju međusobno zavisni, pa je dovoljno da ih samo jednom rešite, da bi Vaš rad bio lakši i brži.

Postoji velika klasa problema koje je moguće rešiti tako što se polazni problem podeli na potprobleme, a oni dalje na pot-pot-probleme i sve tako dok se ne stigne do najjednostavnijih problema, koje se ne moraju dalje deliti i koji se odmah rešavaju. Divide-and-conquer je jedan od metoda koji "radi" na ovom principu Quick sort.

Realno je očekivati da postoje problemi kod kojih se dešava da prilikom deobe na potprobleme se neke pojave više puta. Ukoliko bi svaki bi rešavan onog trenutka kada se na njega naiđe, ne vodeći računa o tome da li je već jednom rešen, moglo bi se desiti da isti posao rađen više puta, što može rezultirati katastrofalno sporim algoritmom.

Osnovna ideja na koju se oslanjaju algoritmi dinamičkog programiranja je da se svaki dobijeni međurezultat (rešenje nekog potproblema) sačuva i potom, kada se sledeći put naiđe na taj isti potproblem, izbegne njegovo ponovno rešavanje. Već sada se uočava bitna razlika između dinamičkog programiranja i divide-and-conquer metoda: kod ovog drugog potproblemi su međusobno nezavisni, dok kod dinamičkog programiranja nisu.

sa sajta Jelene Grmuše

Memoizacija

Izbegavanje ponovnog rešavanja problema naziva se "rekurzija sa pamćenjem" (memoization). To je moguće implementirati uvođenjem pomoćnog globalnog niza ili matrice u kojima pamtimo već izračunato.

U delu o rekurziji, pokazan je i rekurzivan algoritam za izračunavanje fibonačijevih brojeva, koji je veoma spor i neefikasan.

Sada ćemo memoizaciju prikazati na primeru generisanja fibonačijevog niza dinamičkim programiranjem, za x >= 2 :

Const N = 1000;

Var Memo : array[0..N] of longint;

Function Fibonaci(x:integer):longint;

Begin

  If Memo[x-1] = 0

    then Memo[x-1] := Fibonaci(x-1);

  Fibonaci := Memo[x-1] + Memo[x-2];

End;

Begin

  FillChar(memo, SizeOf(memo), 0);

  Memo[0] := 1;

  Memo[1] := 1;

  Writeln(Fibonaci(45));

End.

Na ovaj način, funkcija "FIBONACI" je bila pozvana 44 puta za N = 45, dok je u verziji sa čistom rekurzijom, za isti broj N pozivana više od 2 milijarde puta. U stvari tip LongInt nije mogao prebrojati broj rekurzivnih poziva. Otkud tolika drastična razlika? 45 je relativno mali broj N ali je broj rekurzivnih poziva po dva za svaki broj što je u stvari 2⁴⁵. Dinamičkim programiranjem popunjavamo jednodimenzioni niz, a za svaki član niza imamo po jedan poziv, što je u stvari N-1 tj 44 poziva.

Algoritmi

Grafovi