Module 32
Advanced DP
State machines for stock trading, interval DP for bursting and cutting, DP on trees, and bitmask DP over subsets.
Once 1D, grid, knapsack and sequence DP feel natural, the remaining DP problems mostly differ in what the state looks like. A state machine adds "which mode am I in" to each day. Interval DP solves every range [i, j] by choosing the last (or first) split. Tree DP returns a small tuple from each subtree. Bitmask DP uses an integer to remember which of up to ~20 items are used.
This module teaches each of those four shapes with a lesson and problems, so that a new hard DP problem becomes a matter of choosing the right state.
Best after: DP on Strings and Sequences
Part 1
Learn the ideas
- 32.1State Machine DPWhen each day you can be in one of a few modes (holding stock, just sold, resting), keep the best value for each mode and update them together from the previous day.14 min
- 32.2Interval DP: Choose the Last Splitdp[i][j] = best answer for the range i..j, built from smaller ranges by trying every split point k. Fill by increasing length.14 min
- 32.3DP on TreesEach subtree returns a small tuple, such as (best if this node is used, best if not), and the parent combines its children's tuples.12 min
- 32.4Bitmask DP over SubsetsFor up to about 20 items, an int mask records which items are used. dp[mask] (or dp[mask][last]) has 2ⁿ states.12 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
A three-state machine updated daily.
Two states, with the fee paid on each sale.
A transaction counter in the state: k (buy, sell) pairs.
Interval DP with the "last one to burst" choice.
Interval DP over cut positions: each cut costs the current segment's length.
Tree DP returning (rob, skip) from every subtree.
Three states per node; the bottom-up rule places cameras on the parents of leaves.
dp[mask] = filled amount of the current bucket after using the items in mask.
BFS over (node, visited-mask) states: a bitmask in a graph search.