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.

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 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,

h2. Programare dinamica cu reducerea loop-ului interior

Sa incepem cu urmatoarea problema:

Să considerăm următoarea problema:
h3(#problema-1). Problema 1: 'Drilling':http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en
 
bq. Se da un şir de $N$ numere naturale $(a{~1~}, a{~2~}, ..., a{~N~})$. Se ştie că un prefix al acestui şir (posibil chiar prefixul nul) este prost. Se ştie de asemenea că se poate testa orice poziţie $i$ în timp $a{~i~}$ dacă este proastă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este prost.
 
h3. Exemplu:
 
Pentru secvenţa de numere $(8 24 12 6)$, răspunsul ar fi $(9, -2, 1, 7, 8)$.
 
h3. Rezolvare:

h2. Programare dinamica folosind bitmask