Advanced Dynamic Programming
Classic DP: the 0/1 knapsack in O(n·W) and the longest increasing subsequence in O(n log n).
One level up — DP with two parameters and DP with optimizations. Let's cover two problems every competitive programmer must know.
The 0/1 knapsack: n items with weight and value, a knapsack of capacity W; each item is taken once; maximize the value.
State: dp[cap] — the maximum value at capacity cap. For each item we update dp: either skip it (nothing changes) or take it — then dp[cap] = dp[cap - w] + cost.
The subtlety the problem is famous for: the inner loop over capacity runs TOP-DOWN. Otherwise the item manages to be "packed" twice in one pass.
The 0/1 knapsack. Enter: 4 8, then "weight value" pairs: 3 4, 4 5, 5 6, 2 3
The answer on the example: 10 (the items of weight 3 and 5: values 4 + 6). The complexity is O(n·W) — note that it depends on the NUMERIC value of the capacity, so the knapsack is fine with W up to millions but helpless at W = 10¹⁸.
The second classic — the longest increasing subsequence (LIS). Everyone knows the naive O(n²) DP; the contest version is O(n log n): keep an array tail, where tail[k] is the smallest possible ending of an increasing subsequence of length k+1. Every new element either extends the best subsequence or improves someone's ending — the position is found by binary search.
LIS in O(n log n). Enter: 8, then 10 9 2 5 3 7 101 18
The answer on the example: 4 (for instance, 2 3 7 18). It is important to understand: tail is NOT the subsequence itself, only the "best endings"; but its length always equals the length of the LIS.
How to invent DP states: ask yourself what MINIMUM information about the prefix of the solution is enough to continue optimally. That is exactly the state's parameters.
Task: output not the length of the LIS but the subsequence itself (store, for each element, whom it extended).
Mark the lesson as completed.