def solve(state, memo={}): if state in memo: # 1. cache check return memo[state] if is_base(state): # 2. base case return base_value(state) ans = combine(solve(smaller_state, memo) for ...) # 3. recurse memo[state] = ans # store before returning return ans
Step 1 — Write the math recurrence.F(n)=F(n−1)+F(n−2),F(0)=0,F(1)=1Why this step? Memoization is just a faithful transcription of a recurrence into code. No recurrence ⇒ nothing to memoize.
Step 2 — Translate directly to recursion.
def fib(n): if n < 2: return n return fib(n-1) + fib(n-2)
Why this step? This is correct but exponential. We now attach memory.
Step 3 — Add the cache.
def fib(n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] # cache check if n < 2: return n # base case memo[n] = fib(n-1, memo) + fib(n-2, memo) # recurse + store return memo[n]
Why this step? Each distinct n from 0 to N is computed once. After that it's a dict lookup.
What two properties must a problem have for memoization to help?
Optimal substructure AND overlapping subproblems.
What are the 3 parts of every memoized function?
(1) cache check, (2) base case, (3) recurse-combine-and-store.
Why does memoization turn O(2n) Fibonacci into O(n)?
Each distinct state is computed once; later requests are O(1) cache lookups. Time = #distinct states × work-per-state.
Why is def f(n, memo={}) dangerous in Python?
The default {} is created once and shared across all calls, so the cache persists between independent invocations and can return stale results.
What must the memo key contain?
Every parameter that affects the subproblem's answer (e.g. a tuple (r,c) for 2-D state).
Difference between top-down and bottom-up DP?
Top-down recurses from the goal and caches lazily (only needed states); bottom-up iteratively fills a table from base cases.
In Climbing Stairs, why is the base case W(0)=1?
There is exactly one way to climb zero stairs — do nothing.
What's the space cost of memoized recursion?
O(#distinct states) for the cache + O(recursion depth) for the call stack.
Recall Feynman: explain to a 12-year-old
Imagine doing a hard maths worksheet where the same little sum, like "3+4", appears 50 times. A silly kid recomputes "3+4" every single time. A smart kid writes the answer "7" on a sticky note the first time, and after that just reads the sticky note. Memoization is the sticky-note trick for a computer: solve a small piece once, stick the answer in a notebook (the memo dict), and never do that piece again. The program goes from "forever slow" to "blazing fast" just by remembering.
Dekho, memoization ka idea bahut simple hai: recursion + ek cache (memo dict). Jab tum koi problem chhote-chhote subproblems mein todte ho (jaise Fibonacci), tab same subproblem baar-baar aata hai. Naive recursion har baar usko dobara compute karta hai — isiliye time exponential ho jata hai, jaise fib(40) minute-minute le leta hai. Smart trick: jab tum fib(3) pehli baar nikaalo, uska answer ek dictionary mein save kar lo. Agli baar koi fib(3) maange to seedha dict se padh lo — O(1) mein. Bas itna sa change aur poora algorithm O(2^n) se O(n) ban jaata hai.
Har memoized function ke 3 parts yaad rakho — C-B-R-S: pehle Cache check (kya ye state pehle solve ki thi? to wahi return karo), phir Base case (sabse chhota input jiska answer pata hai), phir Recurse karke subproblems se combine karo, aur sabse important — answer ko Store karo dict mein return karne se pehle. Agar store karna bhool gaye to cache khaali rahega aur koi fayda nahi.
Do bade dhyan dene wale points: pehla, memo key mein un sabhi variables ko daalo jo answer ko affect karte hain. Grid paths mein state (r, c) hai, sirf r se kaam nahi chalega — warna galat purana answer mil jayega aur code chalega lekin chup-chaap galat hoga (yahi sabse khatarnaak bug hai). Doosra, Python mein def f(n, memo={}) mat likho — wo {} ek hi baar banta hai aur saari calls mein share hota hai, isse tests mein galat result aa sakta hai. Iske jagah memo=None rakho aur andar if memo is None: memo = {} karo. Yaad rakho: memoization sirf tab kaam karta hai jab problem mein overlapping subproblems ho — agar har subproblem alag hai (jaise merge sort), to caching ka koi matlab nahi.
