Dynamic programming (memoization اور tabulation) کیا ہے؟

Question

Accepted Answer

**Dynamic programming (DP)** **overlapping subproblems** اور **optimal substructure** والے مسائل کو حل کرتا ہے جو ہر subproblem کو ایک بار compute کرتے ہوئے نتیجہ کو دوبارہ استعمال کرتا ہے۔ دونوں طریقے **memoization** (top-down) اور **tabulation** (bottom-up) ہیں۔

## خیال

Naive recursion ایک جیسے subproblems کو exponentially دوبارہ compute کرتا ہے۔ DP انہیں cache کرتا ہے، exponential کام کو polynomial میں تبدیل کرتے ہوئے۔

## Memoization (top-down)

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## Tabulation (bottom-up)

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## Memoization بمقابلہ tabulation

| | Memoization | Tabulation |
|---|------------|------------||
| سمت | top-down recursion | bottom-up iteration |
| Computes | صرف ضروری states | تمام states |
| خطرہ | stack overflow | کوئی نہیں |
| Space | کاٹا جا سکتا ہے | اکثر O(1) rows میں کم کیا جا سکتا ہے |

## Complexity

Fibonacci: O(2ⁿ) naive سے **O(n)** time، O(n) (یا O(1)) space تک۔

## کب استعمال کریں / نقصانات

DP استعمال کریں جب subproblems **overlap** کریں۔ state اور recurrence کو احتیاط سے define کریں — یہ مشکل حصہ ہے۔ اگر subproblems overlap نہ کریں، تو سادہ divide-and-conquer کافی ہے۔

## اہمیت

DP ناممکن exponential مسائل — shortest paths، edit distance، knapsack — کو efficient بناتا ہے۔

State اور recurrence کو پہچاننے کی مہارت algorithm interviews میں سب سے قیمتی ہے۔

یہ diff tools سے لے کر bioinformatics sequence alignment تک حقیقی systems میں بنیاد رکھتا ہے۔