Dynamic Programming

Core Deep

Dynamic programming is about choosing a state that captures exactly what still matters.

Use This Area When

• greedy feels unsafe but the remaining information can be summarized
• the answer depends on overlapping subproblems
• the real challenge is state design, not raw graph traversal or data-structure maintenance

Start With One Route

If your bottleneck is...	Open first	Then
you still need the DP mindset itself	DP Foundations	Knapsack Family
subset-state problems	Bitmask DP	SOS DP, FWHT / XOR Convolution / Subset Convolution
structural state on trees or ranges	Tree DP	Interval DP, Digit DP
optimization-heavy DP	Divide and Conquer DP	Knuth Optimization, CHT / Li Chao

Core Progression

1. Core first
2. DP Foundations
3. Knapsack Family

4. Bitmask DP

5. Then add

6. Tree DP
7. Digit DP
8. Interval DP

9. SOS DP

10. Deep later

11. FWHT / XOR Convolution / Subset Convolution
12. Bit-Parallelism / Bitset Optimization
13. Broken Profile / Plug DP
14. Divide and Conquer DP / Knuth
15. CHT / Li Chao / LineContainer
16. Slope Trick / Aliens Trick

Good First Repo Anchors

• TFIELD
• Compatible Numbers
• Bitwise XOR Convolution
• School Excursion
• Ciel and Gondolas
• Snuketoon

Browse All Subtopics

• DP Foundations
• Knapsack Family
• Bitmask DP
• SOS DP
• FWHT / XOR Convolution / Subset Convolution
• Bit-Parallelism / Bitset Optimization
• Broken Profile / Plug DP
• Tree DP
• Digit DP
• Interval DP
• Divide and Conquer DP
• Knuth Optimization
• Convex Hull Trick / Li Chao Tree
• Slope Trick
• Lagrangian Relaxation / Aliens Trick

Go Deeper

• Course: Stanford CS161
• Course: Cornell CS 4820
• Practice: AtCoder
• Reference: USACO Guide