Dynamic Programming

दो शर्तें

DP तब लागू होता है जब समस्या में हो (1) इष्टतम उप-संरचना — सर्वश्रेष्ठ उत्तर उप-समस्याओं के सर्वश्रेष्ठ उत्तरों से बनता है — और (2) अतिव्यापी उप-समस्याएँ — वही उप-समस्या बार-बार आती है। हर उप-समस्या का उत्तर cache करें ताकि एक बार गणना हो।

Top-down: memoisation

Recursion लिखें, फिर cache जोड़ें। Fibonacci O(2^n) से O(n) हो जाता है।

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Bottom-up: tabulation

Base case से ऊपर की ओर table भरें। अक्सर आप केवल अंतिम एक-दो पंक्तियाँ रख सकते हैं — स्थान O(1) तक घटाकर।

def climb_stairs(n):     # ways to climb, 1 or 2 steps
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Output:

climb_stairs(5) -> 8

DP से कैसे निपटें

1. State परिभाषित करें (इंडेक्स का क्या अर्थ?)। 2) Transition लिखें (state छोटे states पर कैसे निर्भर?)। 3) Base case तय करें। 4) मूल्यांकन क्रम तय करें। क्लासिक: knapsack, LCS, edit distance, coin change, LIS।