Probabil cea mai utilizata tehnica de programare in concursurile de algoritmi pentru problemele care implica recursivitate este programarea dinamica.
Cea mai cunoscuta problema care se poate rezolva prin programare dinamica este sirul lui fibonacci, care poate fi rezolvata prin recursivitate si are complexitate O(2^n) sau prin programare dinamica si are complexitate O(n), in varianta recursiva calculam aceleas valori de mai multe ori pe cand in varianta iterativa calculam noua valoare pe baza valorilor calculate anterior.
O alta problema interesanta care se rezolva prin programare dinamica este calculul numarului de triangularizari posibile a unui poligon cu (n+2) varfuri astfel incat ca diagonalele sa nu se intersecteze si se calculeaza prin numarul lui catalan de n:
Poate cea mai simplă - şi probabil la fel de cunoscută - problemă care se poate rezolva prin programare dinamică, este problema sumei maxime a triunghiului parcurs de la vârf la bază.
Această problemă este celebră pentru faptul că a constituit pentru prima oară un subiect la Olimpiada Internaţională de Informatică care implica programare dinamică; mai exact: cu ocazia ediţiei din 1994.
