Dynamic Programming Ladders¶
These ladders follow the DP path from state design to structured variants.
Recommended Order¶
- foundations
- knapsack family
- bitmask DP
- tree DP
- digit DP
- interval DP
- SOS DP
- FWHT / xor convolution / subset convolution
- bit-parallelism / bitset optimization
- broken profile / plug DP
- divide and conquer DP
- Knuth optimization
- CHT / Li Chao
- slope trick
- Lagrangian relaxation / Aliens trick
- sliding window / mixed optimization notes
Subtopic Ladders¶
- DP foundations
- Knapsack family
- Bitmask DP
- SOS DP
- FWHT / XOR Convolution / Subset Convolution
- Bit-Parallelism / Bitset Optimization
- Tree DP
- Digit DP
- Interval DP
- Broken Profile / Plug DP
- Divide and Conquer DP
- Knuth Optimization
- CHT / Li Chao
- Slope Trick
- Lagrangian Relaxation / Aliens Trick
- Sliding window
Representative Solved Note¶
- VMSCALE: exact budget DP for a non-uniform comparison tree
- Ciel and Gondolas: partition DP with monotone split optimization on each row
- Knuth Division: split-point interval DP with additive interval cost and Knuth opt windows
- Counting Tilings: frontier-mask DP on a small-width grid
- Compatible Numbers: complement-mask witness propagation over all submasks of the bitwise complement
- Bitwise XOR Convolution: exact boolean-cube transform route once pair-combining under xor replaces one-array SOS sweeps
- School Excursion: DSU component sizes collapsed into one packed boolean reachability row
- Line Add Get Min: direct full-domain line-container verifier inside the affine-DP family
- Monster Game II: affine-DP optimization via online line insertion and point queries
- Snuketoon: convex piecewise-linear DP updated by one-sided hinge penalties and bounded movement
- Red and Blue Lamps: exact-
Rnon-adjacent picks recovered from a penalized linear DP - TFIELD: weighted window reasoning over sorted polygon layers