De ce contează?
Imaginează-ți că rezolvi la tablă o problemă grea și, pe parcurs, îți tot apare aceeași sumă de calculat: „cât face 8 × 7?”. Prima dată o calculezi, apoi o notezi pe o foaie. Data viitoare când ai nevoie de ea, nu o mai refaci — o citești din foaie. Memoizarea e exact această foaie: recursia ta naturală rămâne neschimbată, dar de fiecare dată când termină de calculat un rezultat, îl notează; iar la următoarea cerere îl returnează direct, fără să refacă munca.
Intuiția
Multe probleme se definesc recursiv prin subprobleme mai mici — dar aceleași
subprobleme reapar de multe ori. Recursia naivă le recalculează de fiecare
dată, irosind timp exponențial. Ideea memoizării: păstrezi recursia exact așa
cum e, dar adaugi un „carnețel” (un vector memo) în care scrii fiecare
rezultat prima dată când îl calculezi. La orice reapel al aceleiași subprobleme,
îl citești din carnețel. Fiecare subproblemă se calculează astfel o singură
dată.