Programarea dinamică, când se referă la domeniul informaticii, descrie un grup de algoritmi de computer similari meniți să rezolve probleme complexe prin descompunerea problemei în seturi de probleme mai mici. Creată pentru prima dată de Richard Bellman în anii 1950, programarea dinamică funcționează cu probleme care sunt fie subprobleme suprapuse, fie substructuri optime. Pentru a înțelege cum funcționează programarea dinamică, cel mai bine este să înțelegeți conceptul din spatele acestor doi termeni.
Subproblemele care se suprapun descriu ecuații complicate care, atunci când sunt împărțite în seturi mai mici de ecuații, reutilizează părți ale ecuațiilor mai mici de mai multe ori pentru a ajunge la un răspuns. De exemplu, o ecuație matematică spusă să calculeze toate rezultatele posibile folosind un set de numere poate calcula același rezultat de mai multe ori, în timp ce calculează alte rezultate doar o singură dată. Programarea dinamică ar spune acestei probleme că, după calcularea rezultatului prima dată, ar trebui să salveze acel rezultat și să introducă răspunsul în ecuație mai târziu, în loc să îl calculeze din nou. Când aveți de-a face cu procese și ecuații complexe lungi, acest lucru economisește timp și creează o soluție mai rapidă folosind mult mai puțini pași.
Substructurile optime creează o soluție prin găsirea celui mai bun răspuns la toate subproblemele și apoi creând cel mai bun răspuns general. După ce descompune o problemă complexă în probleme mai mici, computerul folosește apoi un sistem matematic pentru a determina care este cel mai bun răspuns pentru fiecare problemă. Acesta calculează răspunsul la problema inițială din răspunsurile mai mici. Există defecte în acest proces. Deși oferă soluția care funcționează cel mai bine din punct de vedere matematic, poate fi sau nu cea mai bună soluție în viața reală, în funcție de tipul de problemă și de modul în care aceasta se raportează la lumea reală.
În timpul oricăreia dintre aceste operațiuni, algoritmul de programare dinamică încearcă să găsească calea cea mai scurtă către soluție. Poate fi nevoie de una dintre cele două abordări pentru a face acest lucru. Abordarea de sus în jos descompune ecuația în ecuații mai mici și reutiliza răspunsurile pentru aceste ecuații atunci când este necesar. Abordarea de jos în sus încearcă să rezolve cea mai mică valoare matematică după defalcarea ecuației și apoi se îndreaptă spre cea mai mare de acolo. Ambele abordări economisesc timp, dar programarea dinamică funcționează doar atunci când problema inițială se poate descompune în ecuații mai mici care la un moment dat sunt reutilizate pentru a rezolva ecuația.