De ce contează?
Vrei să numeri câte trasee diferite duc din orașul tău până la mare, pe o rețea de drumuri cu sens unic. Ai putea să pornești la drum și să încerci fiecare traseu pe rând — dar sunt mult prea multe. Trucul: dacă știi deja câte trasee ajung în fiecare oraș dinaintea mării, atunci numărul de trasee care ajung la mare e pur și simplu suma lor. Singura grijă: trebuie să afli orașele „mai devreme” înaintea celor „mai târziu”. Sensul unic al drumurilor îți dă exact această ordine.
Intuiția
Un graf orientat aciclic (DAG) e o rețea de noduri cu arce orientate, în care
nu poți reveni niciodată la un nod de unde ai plecat. Pe un astfel de graf, multe
întrebări („câte drumuri?”, „cel mai lung drum?”) au un răspuns care se construiește
nod cu nod: răspunsul pentru un nod depinde doar de predecesorii lui. Dacă
predecesorii sunt deja rezolvați, nodul curent e o simplă combinație a lor. Asta
e DP — doar că „subproblema mai mică” nu mai e un index i-1, ci un nod care vine
înaintea ta în ordinea grafului.
Orice DP cere o ordine în care mergi doar înainte, fără întoarceri. Pe vectori,
ordinea e gratis: 0, 1, 2, …. Pe un DAG, rolul ei îl joacă ordinea topologică
— „ordinea temporală” în care orice arc u → v merge dinspre trecut spre viitor.
Un ciclu ar însemna o dependență circulară: dp[u] cere dp[v] și invers,
deci DP-ul devine imposibil fără o prelucrare prealabilă.