DP -> Digit DP¶

Count or optimize over numeric ranges by scanning digits left-to-right with tight and leading-zero flags.

Microtopics¶

Source	Type
USACO Guide Digit DP	`Reference`
OI Wiki Digit DP	`Reference`

Source	Type
AtCoder DP S	`Practice`
CSES Counting Numbers	`Practice`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Almost Everywhere Zero	`AtCoder Beginner Contest 154`	`Medium`	-	-	-	Tight DP; Count Digits	count numbers by non-zero digit count
Digit Sum	`AtCoder DP Contest`	`Medium`	-	-	-	Tight DP; Mod Sum	classic tight digit DP
Digit Products	`AtCoder Beginner Contest 208`	`Hard`	-	-	-	Tight DP; Digit Product	digit DP with product constraint
Digit Sum Divisible	`AtCoder Beginner Contest 336`	`Hard`	-	-	-	Tight DP; Sum+Remainder	strong digit-DP state compression

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Counting Numbers	`CSES`	`Medium`	Tight-DP	Memoization; Tabulation	Leading Zeros; State Compression	Tight; Adjacency Constraint	tight DP with forbidden adjacent equals

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Find Integers	`LeetCode`	`Medium`	Binary-DP	Memoization	Binary Representation; State Transition	Binary; Fibonacci-Like	A nice non-decimal digit DP that shows the same idea works on binary digits too.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Numbers At Most N Given Digit Set	`LeetCode`	`Medium`	Counting	Memoization	Place-Value Reasoning; Combinatorics	Combinatorics	A very approachable digit-style counting problem that is often solved with a digit DP mindset.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Numbers With Repeated Digits	`LeetCode`	`Hard`	Unique-Digits	Memoization	Count Special Integers; Combinatorics	Combinatorics	A standard follow-up that reinforces counting the complement via digit-state enumeration.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Beautiful Numbers	`Codeforces`	`Very Hard`	Prime-Mask-DP	Memoization	Digit DP Basics; Number Theory	Number Theory	A harder digit DP classic that adds a strong arithmetic twist to the usual tight-state structure.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Segment Sum	`Codeforces`	`Very Hard`	Range-Aggregation	Memoization	Digit DP Basics; Prefix Sums	Sum	A stronger range-counting digit DP that mixes digit states with numeric aggregation.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Count Special Integers	`LeetCode`	`Hard`	Unique-Digits	Memoization	Tight State; Bitmasking	Bitmask	A great bridge between digit DP and bitmasking because the repeated-digit constraint matters.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Digit Sum	`SPOJ`	`Medium`	Range-Counting	Memoization	Tight State; Prefix Digit Reasoning	Sum	A classic range-counting digit DP that makes the tight-bound idea feel concrete.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Magic Numbers	`Codeforces`	`Medium-Hard`	Mod-Constraint	Memoization	Modular Arithmetic; Leading Zeros	Mod	A canonical digit DP where the digit choices are constrained by both adjacency and divisibility rules.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Travelling Salesman and Special Numbers	`Codeforces`	`Medium-Hard`	Counting	Memoization	Tight State; Digit Enumeration	-	A very common digit DP problem that reinforces how to count objects with digit-based restrictions.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Rotated Digits	`LeetCode`	`Medium`	Counting	Memoization	Digit Filtering; State Encoding	Rotation	Useful for learning how to track a small property of each digit while counting up to a bound.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`COUNTINGNUMBERS`	Counting Numbers	`primary`	`medium`	digit dp; previous digit state; range counting	Note	Code

python3 scripts/generate_problem_catalog.py