De ce contează?
Înainte să gătești după o rețetă, pui pe masă ingredientele de start: dacă pleci
cu sare în loc de zahăr, tot ce urmează iese greșit, oricât de corect amesteci.
La fel în programarea dinamică: tabelul dp pornește de la câteva valori de
start — cazurile de bază. Dacă alegi greșit valoarea de pornire, fiecare pas
care se sprijină pe ea moștenește eroarea. Inițializarea e „sarea sau zahărul"
DP-ului.
Intuiția
Un tabel dp se construiește din aproape în aproape: fiecare poziție nouă se
calculează din cele dinainte. Dar prima cărămidă nu se calculează din nimic — o
pui tu de mână. Asta e inițializarea: valorile de start, cunoscute trivial.
Sunt două lucruri de pus corect. Întâi, cazul de bază dp[0] — răspunsul
pentru cea mai mică situație posibilă. Apoi, restul tabelului, pe care îl
umpli cu o valoare care „nu deranjează" calculul: elementul neutru al operației.