DP -> Foundations¶

State design, transitions, and the discipline of converting brute force recurrence thinking into efficient DP.

Microtopics¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Grid 1	`AtCoder DP Contest`	`Easy-Medium`	Grid DP	Tabulation	2D Arrays; Basic Counting	Path Counting	Warm-up grid counting DP before harder path variants.
LCS	`AtCoder DP Contest`	`Medium`	String DP	Tabulation	2D Arrays; String Indexing	2D DP	Warm-up 2D string DP before richer edit-style transitions.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Climbing Stairs	`LeetCode`	`Easy`	Linear DP	Memoization; Tabulation	Basic Recursion; Arrays	Recurrence; 1D	The canonical one-state recurrence: each step depends only on the previous one or two states.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Vacation	`AtCoder DP Contest`	`Easy`	State DP	Tabulation	Arrays; Basic Recurrence	Choices; Day-By-Day; 2D DP; Daily Choice	Introduces multi-state DP where each day carries a small fixed set of options.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
House Robber	`LeetCode`	`Medium`	Linear DP	Tabulation; Rolling-Array	Arrays; Max/Min Reasoning	Skip-Take; Optimization	A compact skip-take DP that is easy to derive and easy to optimize to O(1) space.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dice Combinations	`CSES`	`Easy`	Counting DP	Tabulation	Basic Recursion; Modular Arithmetic	Counting; Mod	Shows how counting DP turns a simple last-move recurrence into an efficient linear solution.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Unique Paths	`LeetCode`	`Medium`	Grid DP	Tabulation	2D Arrays; Basic Counting	Grid; Combinatorics	The standard grid-counting DP that teaches how to propagate answers from left and up.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Longest Common Subsequence	`CSES`	`Medium`	String DP	Tabulation	2D Arrays; String Indexing	2D	A classic 2D DP over prefixes with match-vs-skip transitions.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Edit Distance	`CSES`	`Hard`	String DP	Tabulation	LCS; 2D Arrays	Transformations	A foundational edit DP that generalizes prefix transitions to insert/delete/replace.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Teamwork	`USACO Gold`	`Easy`	Segmented DP	Tabulation	Prefix Sums; Arrays	Partitioning; Bounded-Lookback	A classic segmented DP where each position considers a short backward range of choices.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Frog 2	`AtCoder DP Contest`	`Easy`	Linear DP	Tabulation	Frog 1; Arrays	Min-Cost; Windowed-Transition; 1D DP; Bounded Jump	Builds the same recurrence idea with a wider jump window, which is a common DP stepping stone.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Frog 1	`AtCoder DP Contest`	`Easy`	Linear DP	Tabulation; Memoization	Arrays; Absolute Difference	Min-Cost; Recurrence; 1D DP	A perfect first min-cost DP with a very small transition set and clear base cases.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`QOS`	Chất lượng dịch vụ	`secondary`	`hard`	shortest path plus dp; kth lexicographic path; bounded slack states	Note	Code
`VMSCALE`	Chiếc cân kỳ diệu	`primary`	`hard`	budget dp; balanced ternary; decision-tree optimization	Note	Code

python3 scripts/generate_problem_catalog.py