Memoisation: recursieve resultaten cachen

Python biedt @functools.lru_cache(maxsize=None) (ook beschikbaar als @functools.cache in Python 3.9+) om memoization te automatiseren. Als je deze decorator boven een functie plaatst, worden alle aanroepen opgeslagen op basis van hun argumenten. maxsize=None betekent een onbeperkte cachegrootte — elke unieke combinatie van argumenten wordt opgeslagen. Hiermee verander je elke recursieve functie met één regel code in een memoized versie.

LeetCode 70 'Trappen beklimmen': je kunt telkens 1 of 2 treden beklimmen. Op hoeveel manieren kun je trede n bereiken? Dit is in feite Fibonacci: ways(n) = ways(n-1) + ways(n-2). Basisgevallen: ways(0) = 1 (één manier om op de begane grond te blijven) en ways(1) = 1. Met memoization gebruik je O(n) tijd en O(n) ruimte.

LeetCode 322 'Wisselen met munten': gegeven verschillende muntwaarden en een doelbedrag, vind je het minimale aantal munten. Top-down memoized recursie: dp(amount) = 1 + min(dp(amount - coin)) voor elke geldige munt. Het basisgeval is dp(0) = 0. Sla elk deelbedrag op in de cache. Als een deelbedrag onmogelijk is, retourneer je oneindig. Memoization verandert de exponentiële brute force in O(amount × len(coins)) tijd.

LeetCode 139 'Woorden splitsen': bepaal of een tekenreeks kan worden opgesplitst in woorden uit een woordenboek. Top-down recursie: can_break(s, start) probeert elk voorvoegsel s[start:end]; als dit in het woordenboek staat en can_break(s, end) waar is, retourneer je true. Zonder memoization is dit O(2^n); met memoization (waarbij je elke startindex opslaat) wordt dit O(n² × L), waarbij L de maximale woordlengte is.

Memoization (top-down) begint met het oorspronkelijke probleem en slaat antwoorden op zodra ze recursief worden gevonden. Alleen de deelproblemen die daadwerkelijk nodig zijn, worden opgelost. Tabulatie (van onder naar boven) vult vooraf een tabel in, van kleine naar grote deelproblemen, en lost alle deelproblemen op. Memoization is eenvoudiger af te leiden uit een recursieve oplossing; tabulatie vermijdt beperkingen van de recursiediepte en overhead van functieaanroepen.

Veel problemen met dynamische programmering die met memoized recursie O(n) ruimte gebruiken, kunnen verder worden geoptimaliseerd naar O(1) ruimte wanneer je slechts een vast aantal antwoorden van eerdere deelproblemen nodig hebt. Voor Fibonacci zijn alleen de laatste twee waarden van belang. Voor het beklimmen van trappen geldt hetzelfde. Met twee voortschrijdende variabelen vervang je het volledige memo-woordenboek of de volledige tabel.

Er zijn drie manieren om memoization handmatig te implementeren. Een globaal woordenboek is eenvoudig, maar vervuilt het bereik van de module. Een closure kapselt de cache in binnen de functie, waardoor lekken wordt voorkomen, maar vereist wel een wrapper. @lru_cache is het meest overzichtelijk — één decorator vervangt alle standaardcode. Begin in een interviewcontext met @lru_cache, tenzij de interviewer specifiek om een handmatige implementatie vraagt.

Memoization versnelt alleen problemen met overlappende deelproblemen — gevallen waarin hetzelfde deelprobleem meerdere keren wordt berekend. Als elk deelprobleem uniek is (zoals bij een eenvoudige boomdoorloop waarbij elk knooppunt precies één keer wordt bezocht), voegt memoization overhead toe zonder voordeel. Bovendien kan memoization geen problemen oplossen waarbij de recursieve boom exponentieel is in het aantal verschillende deelproblemen in plaats van in het hergebruik — daarvoor is een volledig ander algoritme nodig.

Pas memoization toe wanneer: je een recursieve oplossing hebt die correct maar traag is door onnodige herberekening, de functie een klein aantal verschillende combinaties van argumenten heeft en de retourwaarde alleen van de argumenten afhangt (een pure functie — zonder bijwerkingen en zonder globale toestand). Controleer de toestandsruimte van de deelproblemen: als er hoogstens O(n) of O(n²) verschillende toestanden zijn, verandert memoization exponentiële tijd in polynomiale tijd.

In deze les heb je geleerd: memoization slaat resultaten van deelproblemen op om herberekening te voorkomen en verandert exponentiële recursie in polynomiale tijd, @functools.lru_cache is het idiomatische Python-hulpmiddel waarvoor slechts één regel nodig is en memoization (top-down) en tabulatie (van onder naar boven) zijn de twee stijlen van dynamische programmering — memoization is eenvoudiger af te leiden en tabulatie voorkomt problemen met de stackdiepte. Gefeliciteerd — je hebt de modules over recursie en hash-maps voltooid!