DP -> Knuth Optimization

O(n^2) optimization for split-point interval DP dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost(l, r)) when the opt window is monotone.

• Topic slug: dp/knuth-optimization
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 6
• Curated external problems: 2

Microtopics

• interval-dp-optimization
• knuth-window
• opt-monotonicity
• quadrangle-inequality
• merge-cost-dp
• rightmost-argmin

Learning Sources

Source	Type
CP-Algorithms Knuth's Optimization	Reference
Competitive Programmer's Handbook	Reference

Practice Sources

Source	Type
CSES Knuth Division	Practice
AtCoder DP N - Slimes	Practice

Repo Companion Material

Material	Type
Knuth Optimization hot sheet	quick reference
Knuth Division	flagship note
Template Library exact starter route	starter route
DP cheatsheet	quick reference
Interval DP tutorial	compare point
Divide and Conquer DP tutorial	compare point

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Knuth Division	CSES	Hard	Interval DP	Interval DP; Cost Preprocessing; Opt Window Monotonicity	Prefix Sums; Split-Point Recurrence	Prefix Sums; Merge Cost	The cleanest first benchmark where the classic merge-cost interval recurrence matches the exact Knuth optimization window.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Slimes	AtCoder DP Contest	Hard	Interval DP	Interval DP; Cost Preprocessing; Optimization Compare Point	Prefix Sums; Split-Point Recurrence	Merge Cost; Prefix Sums; Optimization Compare Point	A canonical compare point with the same merge-style recurrence, useful for seeing the structure before or after importing the stronger Knuth optimization lens.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
KNUTHDIVISION	Knuth Division	primary	hard	-	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py