Chapter 4: Dynamic Programming

Overview

DP is the single most important paradigm in competitive programming. If you could only learn one advanced technique, this would be it. The core idea is simple — avoid recomputing overlapping subproblems — but the art is in designing the right state and transition. This chapter builds from basic 1D recurrences to bitmask DP, digit DP, and tree DP, then goes deep into optimization techniques (Convex Hull Trick, Knuth's, Slope Trick) that separate Expert from Master on Codeforces.

Navigation

Coming from: Chapter 3 — Graph Foundations — BFS, DFS, shortest paths, and MST algorithms
Going to: Chapter 5 — Strings — string hashing, KMP, suffix arrays, and pattern matching
Bridge: BRIDGE-to-advanced.md — transitioning from DP mastery to advanced topics

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	DP Thinking Framework	Beginner	"How do I design a DP state?"
02	DP — 1D Introduction	Beginner	"Fibonacci-like recurrence" or "count ways"
03	DP — Knapsack	Intermediate	"Select items with weight limit to maximize value"
04	2D / Sequence DP	Intermediate	"LIS, LCS, edit distance" — compare two sequences
05	DP — Interval	Intermediate	"Merge stones" or "optimal split of range [l, r]"
06	DP — Bitmask	Intermediate	n ≤ 20 + "assign/use elements from a set" (TSP)
07	DP — Digit	Advanced	"Count integers in [L, R] with digit property"
08	DP on Trees	Intermediate	"Subtree aggregation" or "optimal coloring on a tree"
09	SOS DP	Advanced	"Sum over all subsets" or "for each mask, aggregate submasks"
10	DP — Convex Hull Trick	Advanced	DP recurrence of form dp[i] = min(dp[j] + b[j]·a[i])
11	DP — D&C Optimization	Advanced	"Optimal split point is monotone" in row transitions
12	Slope Trick	Advanced	"Piecewise-linear convex cost function"
13	Knuth's Optimization	Advanced	"Interval DP with quadrangle inequality"
14	Aliens Trick (WQS Binary Search)	Advanced	"Choose exactly k items" + convex cost → Lagrangian relaxation

If You Only Read 3 Files

1. DP Thinking Framework — because knowing how to design a DP matters more than memorizing specific DPs. This file teaches you to identify states, transitions, and base cases systematically.
2. DP — Bitmask — because bitmask DP is the gateway to a whole class of problems (TSP, assignment, subset optimization) and trains you to think about state compression. Appears constantly at CF 1600+.
3. DP on Trees — because tree DP combines graph thinking with DP thinking, and tree problems are among the most common on Codeforces. Understanding subtree aggregation unlocks dozens of problem types.

Cross-Chapter Connections

• The DP Thinking Framework builds directly on Recursion and Backtracking from Chapter 0
• DP — Bitmask requires Bit Manipulation from Chapter 0
• DP on Trees extends into Rerooting Technique in Chapter 10
• DP — Convex Hull Trick can use Segment Tree from Chapter 2 for the Li Chao Tree variant
• Not sure if a problem needs DP or greedy? See the DP vs Greedy Guide in Chapter 11
• DP on DAG in Chapter 3 connects DP with graph structure via topological order

---

File Listing

File	Topic	Level
dp-thinking-framework	DP Thinking Framework	⭐
dp-intro-1d	Dynamic Programming — 1D Introduction	⭐
dp-2d-sequence	2D / Sequence DP (LIS, LCS, Edit Distance)	⭐⭐
dp-knapsack	DP — Knapsack	⭐⭐
dp-on-trees	DP on Trees	⭐⭐
dp-interval	DP — Interval	⭐⭐
dp-bitmask	DP — Bitmask	⭐⭐
dp-digit	DP — Digit	⭐⭐⭐
dp-sos	SOS DP (Sum Over Subsets)	⭐⭐⭐
dp-divide-and-conquer-optimization	DP — Divide and Conquer Optimization	⭐⭐⭐
dp-convex-hull-trick	DP — Convex Hull Trick	⭐⭐⭐
dp-knuth-optimization	Knuth's Optimization	⭐⭐⭐
dp-slope-trick	Slope Trick	⭐⭐⭐
aliens-trick	Aliens Trick (WQS Binary Search)	⭐⭐⭐

Suggested Reading Order

1. dp-thinking-framework — how to design states, transitions, and optimizations
2. dp-intro-1d — overlapping subproblems and memoization basics
3. dp-2d-sequence — LCS, LIS, and Edit Distance
4. dp-knapsack — the archetypal DP problem with weight/value tradeoffs
5. dp-on-trees — subtree DP with post-order traversal
6. dp-interval — optimize over contiguous range splits
7. dp-bitmask — subset enumeration when n ≤ 20
8. dp-digit — count integers with digit-level constraints
9. dp-sos — sum over all subsets via Zeta transform
10. dp-divide-and-conquer-optimization — exploit monotone split points
11. dp-convex-hull-trick — maintain envelope of linear functions
12. dp-knuth-optimization — reduce interval DP via quadrangle inequality
13. dp-slope-trick — optimize convex piecewise-linear DPs
14. aliens-trick — remove "exactly k" constraint via Lagrangian relaxation