DP -> Divide and Conquer DP¶

Monotone-opt partition DP where one row cur[i] = min(prev[k] + cost(k+1, i)) is computed by recursive split-range shrinking.

Microtopics¶

Source	Type
CP-Algorithms Divide and Conquer DP	`Reference`
USACO Guide Divide & Conquer - DP	`Reference`
Competitive Programmer's Handbook	`Reference`

Source	Type
Codeforces Ciel and Gondolas	`Practice`
Codeforces Yet Another Minimization Problem	`Practice`

Material	Type
Divide and Conquer DP hot sheet	`quick reference`
Ciel and Gondolas	`flagship note`
Template Library exact starter route	`starter route`
DP cheatsheet	`quick reference`
Convex Hull Trick / Li Chao Tree tutorial	`compare point`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Ciel and Gondolas	`Codeforces`	`Very Hard`	Partition DP	Partition DP; Cost Preprocessing; Decision Monotonicity	Prefix Sums; Monotone Argmins	Monotone Opt; 2D Prefix Sums; Contiguous Groups	The canonical first benchmark where interval-cost preprocessing and monotone split decisions combine into one exact divide-and-conquer DP row optimization.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Yet Another Minimization Problem	`Codeforces`	`Very Hard`	Partition DP	Partition DP; Cost Maintenance; Decision Monotonicity	Divide And Conquer DP; Incremental Cost Updates; Two Pointers Or Mo Intuition	Monotone Opt; Mo-Style Cost Maintenance; Distinct Pair Cost	A strong follow-up where the row optimization stays the same but the real challenge becomes maintaining the interval cost fast enough.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`CIELANDGONDOLAS`	Ciel and Gondolas	`primary`	`very hard`	-	Note	Code

python3 scripts/generate_problem_catalog.py