h2. Introducere

Programarea dinamica este o metoda utila pentru a rezolva probleme care pot fi obtinute prin compunerea a mai multor bucati, a caror solutie poate fi apoi determinata optim. Se bazeaza in principal pe proprietatea unei probleme de a putea fi rezolvata optim daca se cunosc solutii optime la sub-problemele ei.
De mentionat ca 'programare' nu se refera aici la scrierea de cod intr-un limbaj de programare, si la 'programare matematica', care consta in optimizarea unei functii prin alegerea de valori dintr-un multime anume.

Programarea dinamică este o metodă utilă pentru a rezolva probleme care pot fi obţinute prin compunerea a mai multor bucăţi, a căror soluţie poate fi apoi determinată optim. Se bazează în principal pe proprietatea unei probleme de a putea fi rezolvată optim dacă se cunosc soluţii optime la sub-problemele ei.
De menţionat că 'programare' nu se referă aici la scrierea de cod într-un limbaj de programare, ci la 'programare matematica', care constă în optimizarea unei funcţii prin alegerea de valori dintr-o mulţime anume.

Scopul acestui articol nu este sa ofere o introducere in programare dinamica (pentru aceasta poate fi consultat excelentul tutorial de pe TopCoder "Dynamic Programming : From novice to advanced":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg). In schimb, acest articol isi propune sa ofere niste 'smenuri' mai avansate de rezolvare a problemelor cu programare dinamica,

Scopul acestui articol nu este să ofere o introducere in programare dinamică (pentru aceasta poate fi consultat excelentul tutorial de pe TopCoder "Dynamic Programming : From novice to advanced":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg). În schimb, acest articol îşi propune să ofere nişte 'smenuri' mai avansate de rezolvare a problemelor cu programare dinamică.

h2. Programare dinamica cu reducerea loop-ului interior

h2. Programare dinamică cu reducerea loop-ului interior

Să considerăm următoarea problema: