Digit DP
Counting numbers in huge ranges seems impossible. Digit DP builds answers digit by digit.
Lessons
1. Intro
What you'll learn
2. Core Concept
Digit-by-digit processing
3. Vocabulary - Tight Bound
The key constraint
4. Quiz: Tight Bound
Understanding the constraint
5. Vocabulary - Leading Zeros
Handling shorter numbers
6. Quiz: Leading Zeros
When zeros matter
7. The General Pattern
State template
8. Range Queries
From [L,R] to prefix
9. LeetCode 902 Numbers At Most N Given Digit Set - Problem Statement
LeetCode 902
10. Digit Set - The Setup
Understanding the constraints
11. Digit Set - State Definition
What dp[pos][tight] means
12. Digit Set - Transition
Picking valid digits
13. Digit Set - Implementation
The code
14. Digit Set - Walkthrough
Tracing the algorithm
15. Lessons from Digit Set
summary
16. Challenge: Digit Set Edge Cases
Handling tricky inputs
17. LeetCode 2376 Count Special Integers - Problem Statement
LeetCode 2376
18. Special Integers - The Setup
Tracking used digits
19. Special Integers - State Definition
Adding the mask
20. Special Integers - Transition
Checking the mask
21. Special Integers - Implementation
The code
22. Special Integers - Walkthrough
Tracing distinct digits
23. Lessons from Special Integers
summary
24. Quiz: Bitmask in Digit DP
Why bitmask works
25. LeetCode 600 Non-negative Integers without Consecutive Ones - Problem Statement
LeetCode 600
26. Consecutive Ones - The Setup
Working in binary
27. Consecutive Ones - State Definition
Tracking previous bit
28. Consecutive Ones - Transition
Avoiding 11
29. Consecutive Ones - Implementation
The code
30. Consecutive Ones - Walkthrough
Tracing with previous digit
31. Lessons from Consecutive Ones
summary
32. Challenge: K Consecutive Ones
Generalizing the constraint
33. Pattern - Digit DP
Core idea
34. Digit Sum - Problem Statement
Classic digit DP variant
35. Digit Sum - Implementation
Memoization details
36. Quiz: Digit DP Complexity
Analyzing state space
37. Count Stepping Numbers - Problem Statement
Adjacent digit constraint
38. Stepping Numbers - Implementation
Handling started flag
39. Challenge: Digit DP on Multiple Numbers
Comparing two numbers
40. Pattern - When to Use Digit DP
Recognizing the pattern
41. What's Next
Preview of Game Theory DP
42. Section Recap
What we learned
Practice Problems
Count numbers where digit sum is divisible by D - foundational.
No adjacent same digits - teaches tight bound and leading zeros.
Exactly K non-zero digits - handles N up to 100 digits.
At most 3 non-zero digits - practice count parameter in state.
Restricted digit set - handling which digits can be used.
Positional constraints + divisibility - advanced digit DP.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Count numbers with d at even positions only, divisible by m. Classic digit DP.
Count numbers with at most 3 non-zero digits. Digit DP tracking non-zero count.
Count numbers where all digits appear even times in base b. Multi-base digit DP.
Count pairs where a XOR b = a + b. Two-variable digit DP on binary representation.
Count numbers reaching 1 in exactly k steps via popcount. Digit DP + precomputation.
Sum of numbers using at most k distinct digits. Digit DP tracking digit set.
Count integers with digit sum in range. Standard digit DP with sum tracking.
Adjacent digits differ by 1. Digit DP tracking last digit placed.
Equal even/odd digits and divisible by k. Multi-constraint digit DP.
Count numbers with at least one repeated digit. Complement counting with digit DP.