- Dynamic Programming
- [01 knapsack](#01\ knapsack)
- Longest Common Sequence
- Matrix Chain Multiplication
01 knapsack
weight = {1, 2, 3} value = {10, 15, 40} capacity = 6
| weight⇢ item⇣/ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 # init row | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 10 | 10 | 10 | 10 | 10 | 10 |
| 2 | 0 | 10 | 15 | 25 | 25 | 25 | 25 |
| 3 | 0 | 10 | 15 | 40 | 50 | 55 | 65 |
- copy till
capacity >= item.weight - at every cell fill
MAX(prev_row(a - item.weight) + item.value, value(a))