Chapter 6.5: Digit DP

English translation of this chapter is coming soon. Please refer to the Chinese version for now.

Content Outline

6.5.1 Problem Introduction

• A Common Class of Problems: Counting Numbers with Certain Digit Properties in [1, N]

6.5.2 Framework of Digit DP

• Core State: pos, tight, and Other Properties
• Key Logic for Tight and Non-Tight States

6.5.3 Complete Example 1: Digit Sum Equals S

6.5.4 General Digit DP Template (Concise Version)

6.5.5 Example 2: No Consecutive Identical Digits

• Additional State: last_digit

6.5.6 Example 3: Non-Decreasing Digits

• Additional State: min_digit

6.5.7 Interval Queries: f(R) - f(L-1)

6.5.8 Common Digit DP Problem Types

• Digit sum = S / No specific digit / Adjacent different / Non-decreasing / Exactly k of a digit / Divisibility

Common Mistakes

Exercises

1. Numbers Without Digit 4
2. Numbers with Digit Sum Equal to S
3. Non-Decreasing Digits with Digit Sum <= K
4. USACO Gold Style — Numbers Divisible by M