# Dynamic Programming — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/dynamic-programming

> अतिव्यापी उप-समस्याओं को एक बार हल करें, उत्तर संग्रहीत करें, और ऊपर बनाएँ।

## दो शर्तें

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

## Top-down: memoisation

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

```python
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)` तक घटाकर।

```python
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।