# Advanced Dynamic Programming — Data Structures & Algorithms

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

> Three interview staples — 0/1 Knapsack, Longest Common Subsequence, and Longest Increasing Subsequence.

## 0/1 Knapsack

For each item, decide to **take or skip** it. `dp[w]` tracks the best value achievable with capacity `w`; iterate weight **backward** so each item is used at most once.

```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]` is the LCS length of `text1[:i]` and `text2[:j]`. Matching characters extend the diagonal; otherwise take the best of skipping one character from either string.

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

The `O(n^2)` version tries every previous index. A faster `O(n log n)` version keeps a `tails` array of the smallest tail for each subsequence length, using **binary search** to place each new number.

```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.)
```

## Recognize the shape

Two strings/sequences and a comparison → LCS-style 2D DP. A single sequence with 'increasing/decreasing' → LIS-style. A set of items with a capacity limit → knapsack-style.