8 subtopics · 26 problems
Dynamic Programming — Advanced
Bitmask DP, digit DP, interval DP, tree DP, probability DP, and DP optimizations.
01Bitmask DP
DP over subsets using bitmasks — O(2^n × n).
1 medium3 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1881DDivide and Equalize | medium | Solve |
| 1837DBracket Coloring | hard | Solve |
| 1837EPlayoff Fixing | hard | Solve |
| 580DKefa and Dishes | hard | Solve |
02Digit DP
Count numbers in [L, R] satisfying digit constraints.
3 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1036CClassy Numbers | hard | Solve |
| 855ESalazar Slytherin's Locket | hard | Solve |
| 628DMagic Numbers | hard | Solve |
03Interval DP
DP on subarrays/substrings: dp[l][r] merging intervals.
1 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 607BZuma | medium | Solve |
| 149DColoring Brackets | hard | Solve |
| 1025DRecovering BST | hard | Solve |
04Tree DP
DP rooted on trees — subtree aggregation, rerooting.
2 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1324FMaximum White Subtree | medium | Solve |
| 1328ETree Queries | medium | Solve |
| 1092FTree with Maximum Cost | hard | Solve |
| 1187ETree Painting | hard | Solve |
05DP on DAG
Topological order + DP — longest path, counting paths.
2 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1851DPrefix Permutation Sums | medium | Solve |
| 1881EBlock Sequence | medium | Solve |
| 721CJourney | hard | Solve |
06Probability / Expected Value DP
Compute expected values via DP transitions.
2 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 768BCode For 1 | medium | Solve |
| 1062DFun with Integers | medium | Solve |
| 453ALittle Pony and Expected Maximum | hard | Solve |
07Sum over Subsets (SOS) DP
Efficiently aggregate over all subsets/supersets of each mask.
1 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1554BCobb | medium | Solve |
| 449DJzzhu and Numbers | hard | Solve |
| 165ECompatible Numbers | hard | Solve |
08DP Optimizations
Convex hull trick, divide & conquer optimization, Knuth's optimization.
3 hard
| Problem | Difficulty | Link |
|---|---|---|
| 372CWatching Fireworks is Fun | hard | Solve |
| 868FYet Another Minimization Problem | hard | Solve |
| 319CKalila and Dimna in the Logging Industry | hard | Solve |
Was this helpful?