Memoization (top-down DP) — recursive + memo dict

3.7.7 · Coding › Algorithm Paradigms

WHY karta hai yeh exist?

Woh do conditions jo memoization ko kaam karti hain:

WHAT hai iska structure?

Ek memoized function = 3 parts, hamesha:

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

HOW derive karein scratch se (Fibonacci)

Step 1 — Math recurrence likho. $F (n) = F (n - 1) + F (n - 2), F (0) = 0, F (1) = 1$ Yeh step kyun? Memoization sirf ek recurrence ka code mein faithful transcription hai. Koi recurrence nahi ⇒ kuch memoize karne ko nahi.

Step 2 — Seedha recursion mein translate karo.

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Yeh step kyun? Yeh correct hai lekin exponential hai. Ab hum memory attach karte hain.

Step 3 — Cache add karo.

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]

Yeh step kyun? $0$ se $N$ tak har distinct n ek baar compute hota hai. Uske baad yeh ek dict lookup hai.

Figure — Memoization (top-down DP) — recursive + memo dict

Worked Example 2 — Climbing Stairs

Worked example

n stairs chadne ke kitne tarike hain 1 ya 2 steps lete hue? Recurrence: step $n$ tak pahunchne ke liye tum $n - 1$ (1 step) ya $n - 2$ (2 steps) se aaye. $W (n) = W (n - 1) + W (n - 2), W (0) = 1, W (1) = 1$

def ways(n, memo=None):
    if memo is None: memo = {}
    if n in memo: return memo[n]
    if n <= 1: return 1          # 1 way to "climb" 0 or 1 stairs
    memo[n] = ways(n-1, memo) + ways(n-2, memo)
    return memo[n]

W(0)=1 kyun? 0 stairs "chhadhne" ka exactly ek tarika hai (kuch mat karo). Base case sahi rakhna sabse zyada error-prone part hai — recurrence bekar hai agar base value galat hai.

Worked Example 3 — Grid Unique Paths (2-D state)

Worked example Top-left se bottom-right tak paths, sirf right/down move karte hue.

State ek pair hai (r, c). Recurrence: $(r, c)$ par upar se ya left se pahuncho. $P (r, c) = P (r - 1, c) + P (r, c - 1)$

def paths(r, c, memo=None):
    if memo is None: memo = {}
    if (r, c) in memo: return memo[(r, c)]
    if r == 0 or c == 0: return 1   # only one straight-line path along an edge
    memo[(r, c)] = paths(r-1, c, memo) + paths(r, c-1, memo)
    return memo[(r, c)]

Tuple key kyun? "State" woh hai jo ek subproblem ko uniquely identify kare. Yahan tumhare paas dono coordinates chahiye, isliye cache key (r, c) hai. Rule: memo key mein har woh variable hona chahiye jo answer ko change karta ho — ek bhi miss kiya toh galat cached results return honge.

Top-down vs Bottom-up (quick contrast)

Flashcards

Memoization help karne ke liye ek problem mein kaunsi do properties honi chahiye?

Optimal substructure AND overlapping subproblems.

Har memoized function ke 3 parts kaunse hain?

(1) cache check, (2) base case, (3) recurse-combine-and-store.

Memoization

O (2^{n})

Fibonacci ko

O (n)

mein kyun badal deta hai?

Har distinct state ek baar compute hoti hai; baad ki requests

O (1)

cache lookups hain. Time = #distinct states × work-per-state.

Python mein def f(n, memo={}) dangerous kyun hai?

Default {} ek baar create hota hai aur saari calls mein shared hota hai, isliye cache independent invocations ke beech persist karta hai aur stale results return kar sakta hai.

Memo key mein kya hona chahiye?

Har woh parameter jo subproblem ka answer affect karta ho (jaise 2-D state ke liye ek tuple (r,c)).

Top-down aur bottom-up DP mein kya fark hai?

Top-down goal se recurse karta hai aur lazily cache karta hai (sirf zaroori states); bottom-up iteratively base cases se table fill karta hai.

Climbing Stairs mein base case W(0)=1 kyun hai?

Zero stairs chadne ka exactly ek tarika hai — kuch mat karo.

Memoized recursion ki space cost kya hai?

O(#distinct states) cache ke liye + O(recursion depth) call stack ke liye.

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ek mushkil maths worksheet kar rahe ho jahan ek hi chhota sum, jaise "3+4", 50 baar aata hai. Ek bewaqoof bacha "3+4" har baar dobara compute karta hai. Ek smart bacha pehli baar answer "7" ek sticky note par likhta hai, aur uske baad sirf sticky note padhta hai. Memoization computer ke liye wohi sticky-note trick hai: ek chhota piece ek baar solve karo, answer ek notebook (memo dict) mein chipkao, aur woh piece kabhi mat karo dobara. Program "hamesha slow" se "blazing fast" ho jaata hai sirf yaad rakhne se.

Connections

Recursion — memoization hai recursion with memory
Dynamic Programming — umbrella paradigm
Tabulation (Bottom-up DP) — iterative twin
Time Complexity Analysis — distinct states count karna
Divide and Conquer — recursion bina overlapping subproblems ke
Hash Maps / Dictionaries — cache data structure
lru_cache decorator — Python ka built-in memoization