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

Source: https://www.geekswithgeeks.com/hi/dsa/advanced-dp

> तीन interview के मुख्य विषय — 0/1 Knapsack, Longest Common Subsequence, और Longest Increasing Subsequence।

## 0/1 Knapsack

हर item के लिए, उसे **लेना या छोड़ना** तय करें। `dp[w]`, capacity `w` से मिलने वाला सबसे अच्छा value रखता है; weight को **उल्टा** iterate करें ताकि हर item अधिकतम एक बार इस्तेमाल हो।

```python
def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]
```

Output:

```
knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)  # 9
```

## Longest Common Subsequence

`dp[i][j]`, `text1[:i]` और `text2[:j]` की LCS लंबाई है। मिलते characters diagonal को बढ़ाते हैं; वरना दोनों में से किसी एक string से एक character छोड़ने में जो बेहतर हो वह लें।

```python
def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
```

Output:

```
lcs('abcde', 'ace')  # 3 ('ace')
```

## Longest Increasing Subsequence

`O(n^2)` version हर पिछले index को आज़माता है। तेज़ `O(n log n)` version हर subsequence length के लिए सबसे छोटी tail का `tails` array रखता है, हर नए number को रखने के लिए **binary search** का उपयोग करते हुए।

```python
import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)
```

Output:

```
length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])  # 4  ([2,3,7,101] etc.)
```

## आकार पहचानें

दो strings/sequences और तुलना → LCS-जैसा 2D DP। एक ही sequence में 'बढ़ता/घटता' → LIS-जैसा। Capacity सीमा के साथ items का समूह → knapsack-जैसा।