De ce contează?
Calculezi cu mâna câte drumuri duc spre un colț îndepărtat al unei table. Observi că treci de zeci de ori prin aceleași celule intermediare și refaci de fiecare dată același calcul. Deștept ar fi să notezi rezultatul fiecărei celule pe un bilețel lipit de ea: când ai nevoie din nou, citești biletul în loc să refaci munca. Asta e programarea dinamică — nu rezolvi aceeași subproblemă de două ori, o notezi o dată și o refolosești.
Intuiția
Multe probleme grele se sparg în subprobleme care se repetă. Dacă rezolvi fiecare subproblemă o singură dată și îți notezi răspunsul într-un tabel, eviți munca duplicată. Restul algoritmului devine doar „citesc din tabel ce am calculat deja și combin”. Toată dificultatea DP nu e codul — e să vezi care sunt subproblemele și cum se compun una din alta.