DP -- Digit

Quick Revisit

• USE WHEN: Count/sum integers in $[L,R]$ satisfying a digit-level property (digit sum, specific digit patterns, divisibility)
• INVARIANT: At each position, tight flag tracks whether all prior digits matched $N$ exactly; if tight, next digit ≤ $N$'s digit, else 0–9
• TIME: O(digits × |state| × 10) | SPACE: O(digits × |state|)
• CLASSIC BUG: Forgetting leading-zero handling (e.g., "0047" isn't a 4-digit number), or wrong $f(L-1)$ boundary in range decomposition
• PRACTICE: 04-ladder-dp

AL-31 | Count integers in a range $[0,N]$ that satisfy a digit-level property, one digit at a time, tracking a "tight" flag to stay within bounds.

Difficulty: [Advanced]Prerequisites: DP -- 1D IntroductionCF Rating Range: 1700 -- 2100

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

Count integers in $[1,345]$ whose digit sum $\le 10$.

Naive approach: iterate all 345 numbers, compute each digit sum, check the condition. That works here -- but when the range is $[1,{10}^{18}]$, you face ${10}^{18}$ iterations. Even at ${10}^9$ per second, that's over 30 years. We need a fundamentally different strategy.

Build numbers digit by digit from left to right, tracking only the relevant property (digit sum) and whether we're still bounded by the limit -- this reduces ${10}^{18}$ numbers to $O(\text{digits}\times \text{states})$ DP.

Think of it like filling out a form one digit at a time. Each box on the form is a digit position. As you fill each box, you have a constraint: if every digit you've written so far exactly matches the upper limit $N$, the next digit can only go up to $N$'s corresponding digit. But the moment you write something smaller, you're "free" -- every remaining box can hold any digit $0$--$9$. Meanwhile you carry forward just enough bookkeeping (the running digit sum) to decide validity at the end.

The range $[L,R]$ decomposes as $f(R)-f(L-1)$, where $f(N)$ counts valid numbers in $[0,N]$.

Diagram: The Decision Tree -- Tight vs Free Branching

Upper bound N = 472 (3-digit number)

                         solve(pos=0, tight=T)
                       /     |      \       \        \
                   d=0       d=1     d=2     d=3      d=4
                  FREE      FREE    FREE    FREE     TIGHT
                 /    \    /    \                    /    \
             d=0..9  ...  d=0..9 ...            d=0..6  d=7
               FREE        FREE                  FREE  TIGHT
                                                       /  |  \
                                                   d=0  d=1  d=2
                                                   OK    OK    OK

  TIGHT path: d matches N's digit exactly -> next digit bounded
  FREE  path: d < N's digit -> ALL subsequent digits unconstrained (0-9)

  Only ONE path through the tree stays tight (the one matching
  N exactly: 4 -> 7 -> 2). All other branches become free
  immediately and stay free forever.

  +-------------------------------------------------------+
  | tight=true at pos i means digits 0..i-1 ALL matched N |
  | exactly. The MOMENT you pick d < N[i], tight becomes  |
  | false and can NEVER become true again.                 |
  +-------------------------------------------------------+

Visual Walkthrough

We count integers in $[0,345]$ with digit sum $\le 10$. The upper bound has digits $3$, $4$, $5$. Our DP state is (pos, sum_so_far, tight).

Step 1 -- Position 0 (hundreds digit), tight = true, sum = 0
         Allowed digits: 0..3 (tight, so <= N's digit 3)

         d=0  -> (pos=1, sum=0,  tight=false)   "went below 3 => free"
         d=1  -> (pos=1, sum=1,  tight=false)   "went below 3 => free"
         d=2  -> (pos=1, sum=2,  tight=false)   "went below 3 => free"
         d=3  -> (pos=1, sum=3,  tight=true)    "matched 3 => still tight"

Step 2 -- Position 1 (tens digit), expanding d=3 branch (tight = true)
         Allowed digits: 0..4 (tight, so <= N's digit 4)

         d=0  -> (pos=2, sum=3,  tight=false)
         d=1  -> (pos=2, sum=4,  tight=false)
         d=2  -> (pos=2, sum=5,  tight=false)
         d=3  -> (pos=2, sum=6,  tight=false)
         d=4  -> (pos=2, sum=7,  tight=true)    "matched 4 => still tight"

Step 3 -- Position 1 (tens digit), expanding d=0 branch (tight = false)
         Allowed digits: 0..9 (free!)

         d=0  -> (pos=2, sum=0,  tight=false)
         d=1  -> (pos=2, sum=1,  tight=false)
         ...
         d=9  -> (pos=2, sum=9,  tight=false)

Step 4 -- Position 2 (units digit), example: sum=7, tight=true
         Allowed digits: 0..5 (tight, so <= N's digit 5)

         d=0  -> sum=7  <= 10  VALID
         d=1  -> sum=8  <= 10  VALID
         d=2  -> sum=9  <= 10  VALID
         d=3  -> sum=10 <= 10  VALID
         d=4  -> sum=11 > 10   INVALID
         d=5  -> sum=12 > 10   INVALID
         => This state contributes 4 valid completions.

Many branches share identical (pos, sum, tight) triples -- memoization collapses them. Total states: $3\times 28\times 2=168$ instead of $345$.

Diagram: Tight Constraint Propagation for N = 352

Position 0 (hundreds)     Position 1 (tens)        Position 2 (units)
┌─────────────────┐       ┌──────────────────┐     ┌──────────────────┐
│ N's digit: 3    │       │ N's digit: 5     │     │ N's digit: 2     │
│                 │       │                  │     │                  │
│ d=0 -> FREE ────┼──->────│ d=0..9 (any!) ───┼──->──│ d=0..9 (any!)   │
│ d=1 -> FREE ────┼──->────│ d=0..9 (any!) ───┼──->──│ d=0..9 (any!)   │
│ d=2 -> FREE ────┼──->────│ d=0..9 (any!) ───┼──->──│ d=0..9 (any!)   │
│ d=3 -> TIGHT ───┼──->────│ d=0 -> FREE ──────┼──->──│ d=0..9 (any!)   │
│                 │       │ d=1 -> FREE ──────┼──->──│ d=0..9 (any!)   │
│                 │       │ d=2 -> FREE ──────┼──->──│ d=0..9 (any!)   │
│                 │       │ d=3 -> FREE ──────┼──->──│ d=0..9 (any!)   │
│                 │       │ d=4 -> FREE ──────┼──->──│ d=0..9 (any!)   │
│                 │       │ d=5 -> TIGHT ─────┼──->──│ d=0 OK           │
│                 │       │                  │     │ d=1 OK           │
│                 │       │                  │     │ d=2 OK (TIGHT)   │
└─────────────────┘       └──────────────────┘     └──────────────────┘

The single tight path: 3 -> 5 -> 2 (= N itself = 352)
One step below at ANY position -> freedom for ALL remaining positions.

  d < N[pos]  ──->  tight becomes false  ──->  stays false forever
  d == N[pos] ──->  tight stays true     ──->  next digit still bounded

The diagrams show how the tight flag propagates through the decision tree. We can now state the recurrence precisely.

The Invariant

+----------------------------------------------------------------------+
| dp[pos][sum][tight] = count of valid completions from position pos   |
| with accumulated digit sum 'sum', where tight indicates whether all  |
| previous digits matched the upper bound N exactly.                   |
+----------------------------------------------------------------------+

At any point in the recursion, the answer for the remaining suffix depends only on these three values -- not on which specific prefix led here. This is what makes memoization correct.

What the Code Won't Teach You

The $f(R)-f(L-1)$ trick is the entire range strategy. Every digit DP problem over $[L,R]$ reduces to two prefix queries: count valid numbers in $[0,R]$ and subtract the count in $[0,L-1]$. You never write a DP that directly handles both endpoints -- decompose first, then solve the simpler $[0,N]$ problem twice. This is so universal that you should internalize it as a reflex, not a technique.

The tight boolean encodes constraints on remaining digits, not a property of the number. This is what makes digit DP feel alien compared to other DPs. In knapsack DP, the state describes what you've chosen. In digit DP, the state describes what you're allowed to choose next. The tight flag says: "every digit I've placed so far exactly matches $N$'s prefix, so my next digit is bounded." The moment you place a smaller digit, you're free forever. This constraint-propagation perspective is the real mental model.

Leading zeros are irrelevant for additive properties, critical for structural ones. If you're tracking digit sum, leading zeros contribute 0 and don't affect the answer -- you can ignore them. But if you're tracking "no repeated consecutive digits" or "count of digit $d$", leading zeros create phantom digits that corrupt your state. The rule: if your property would give a different answer for "007" vs "7", you need a started flag.

Digit DP states describe constraints, not numbers. In most DPs, the state represents a subproblem about a concrete object (a subarray, a subset). In digit DP, the state represents "how many ways can I fill the remaining blanks given these constraints on what I'm allowed to place?" The number itself doesn't appear in the state -- only the running aggregate (digit sum, remainder, etc.) and the constraint flag (tight). This is why digit DP feels different: you're counting completions under constraints, not optimizing over choices.

When to Reach for This

Trigger phrases:

• "Count numbers in $[L,R]$ with property $P$"
• "digit sum", "digit product", "count of digit $d$"
• "numbers without digit 4", "non-decreasing digits"
• "divisible by the sum/product of its digits"
• $N$ up to ${10}^{18}$ (too large to iterate)

Counter-examples (NOT digit DP):

• The property doesn't decompose digit-by-digit (e.g., "is prime" -- primality depends on the whole number, not on a running aggregate of digits).
• The problem asks about arithmetic relationships between numbers rather than digit-level properties (e.g., "count pairs $(a,b)$ with $a+b=k$").
• $N$ is small enough to iterate ($\le {10}^7$) and the property is cheap to check -- brute force may be simpler.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
to_string(n)	<string>	Convert integer to digit string	$O(d)$ where $d$ = digits
string::operator[]	<string>	Access individual digit character	$O(1)$
memset(dp, -1, sizeof dp)	<cstring>	Reset memoization array to $-1$	$O(\text{size})$
vector / array	<vector> / <array>	DP table storage	$O(1)$ access
map<tuple<...>, long long>	<map>	Memo for complex state (slower, but flexible)	$O(\log n)$ per lookup
__int128	built-in	For intermediate products if $N>{10}^{18}$	--

---

Implementation (Contest-Ready)

Problem: Count integers in $[0,N]$ whose digit sum equals exactly $K$.

Version 1: Recursive with Memoization -- Minimal Template

⚠️ The tight flag MUST be part of the memoization key. dp[pos][sum] is WRONG if it ignores whether we're still constrained by the upper bound. The correct state is dp[pos][sum][tight]. Without tight in the key, you'll cache a "tight" result and reuse it in an "untight" context (or vice versa), producing wrong counts.

  Upper bound: 345
  At position 1, digit = 3 (tight): next digit can be 0-4
  At position 1, digit = 2 (not tight): next digit can be 0-9

  If you memoize dp[1][sum] without tight, you'll return the tight answer
  for the untight case (or vice versa) -- wrong count.

#include <bits/stdc++.h>
using namespace std;

string num;
int K;
long long memo[20][2][180]; // pos, tight, sum

long long solve(int pos, bool tight, int sum) {
    if (sum > K) return 0;
    if (pos == (int)num.size())
        return sum == K ? 1 : 0;
    if (memo[pos][tight][sum] != -1)
        return memo[pos][tight][sum];

    int lim = tight ? (num[pos] - '0') : 9;
    long long res = 0;
    for (int d = 0; d <= lim; d++)
        res += solve(pos + 1, tight && d == lim, sum + d);

    return memo[pos][tight][sum] = res;
}

// Count of x in [0, N] with digit_sum(x) == K
long long count(long long N) {
    if (N < 0) return 0;
    num = to_string(N);
    memset(memo, -1, sizeof memo);
    return solve(0, true, 0);
}

int main() {
    long long L, R;
    cin >> L >> R >> K;
    cout << count(R) - count(L - 1) << "\n";
}

Version 2: Recursive with Memoization -- Explained

#include <bits/stdc++.h>
using namespace std;

string num;  // digit representation of N
int K;       // target digit sum

// memo[pos][tight][sum]:
//   pos   = current digit index (0 = MSD)
//   tight = 1 if all digits so far match N's prefix exactly
//   sum   = digit sum accumulated so far
// Value: count of ways to complete remaining digits so total sum == K
long long memo[20][2][180];

long long solve(int pos, bool tight, int sum) {
    // Pruning: if sum already exceeds K, no valid completion exists
    if (sum > K) return 0;

    // Base case: placed all digits
    if (pos == (int)num.size())
        return sum == K ? 1 : 0;

    if (memo[pos][tight][sum] != -1)
        return memo[pos][tight][sum];

    // If tight, current digit is bounded by N's digit at this position.
    // Otherwise, any digit 0..9 is valid.
    int lim = tight ? (num[pos] - '0') : 9;

    long long res = 0;
    for (int d = 0; d <= lim; d++) {
        // tight propagates only if we're still matching N's prefix
        // AND we chose the maximum allowed digit.
        res += solve(pos + 1, tight && (d == lim), sum + d);
    }

    return memo[pos][tight][sum] = res;
}

long long count(long long N) {
    if (N < 0) return 0;
    num = to_string(N);
    memset(memo, -1, sizeof memo);
    return solve(0, true, 0);
}

int main() {
    long long L, R;
    cin >> L >> R >> K;
    // f(R) - f(L-1) gives count of valid numbers in [L, R]
    cout << count(R) - count(L - 1) << "\n";
}

---

Operations Reference

Digit DP is remarkably fast -- the table below shows why problems with $N$ up to ${10}^{18}$ finish in microseconds rather than years.

Operation	Time	Space
Digit DP with $d$-digit number, state size $S$	$O(d\cdot 10\cdot S)$	$O(d\cdot S)$
Digit sum = K, $N\le {10}^{18}$	$O(18\cdot 10\cdot 2\cdot 163)\approx O(\mathrm{58,000})$	$O(18\cdot 2\cdot 163)\approx O(\mathrm{6,000})$
Count mod $m$, $N\le {10}^{18}$	$O(18\cdot 10\cdot 2\cdot m)$	$O(18\cdot 2\cdot m)$
$[L,R]$ query via $f(R)-f(L-1)$	$2\times$ single call	same

All complexities assume base-10 representation. For other bases, replace $10$ with the base.

---

Problem Patterns & Tricks

Pattern 1: Digit Sum Constraints

Count numbers in $[L,R]$ with digit sum equal to / at most / at least $K$.

State: (pos, tight, sum_so_far)

This is the canonical digit DP problem. The template in Section 4 solves it directly.

Examples: CF 1036C -- Classy Numbers, CF 855E -- Salazar Slytherin's Locket

---

Pattern 2: Counting Occurrences of a Specific Digit

"How many times does digit $d$ appear in all numbers from $L$ to $R$?"

State: (pos, tight, count_of_d) -- or just accumulate the count directly.

Trick: Instead of counting numbers, count total digit occurrences. At each position, add 1 to the running count if the placed digit equals $d$.

// Inside solve: track cnt = how many times digit d appeared so far
for (int dig = 0; dig <= lim; dig++)
    res += solve(pos + 1, tight && dig == lim, cnt + (dig == d));

Examples: CF 1560F2 -- Nearest Beautiful Number (hard), SPOJ DIGIT -- Counting Digits

---

Pattern 3: Range $[L,R]$ Decomposition

Almost every digit DP problem uses $f(R)-f(L-1)$. Implement a single function count(N) that counts valid numbers in $[0,N]$.

Watch out: If $L=0$, then $f(L-1)=f(-1)$. Handle by returning $0$ when $N<0$.

Examples: Virtually all digit DP problems use this.

---

Pattern 4: Divisibility / Remainder

Count numbers in $[0,N]$ divisible by $m$ (or with remainder $r$).

State: (pos, tight, current_remainder_mod_m)

Transition: new remainder = $(old\cdot 10+d)\mathrm{mod}m$.

long long solve(int pos, bool tight, int rem) {
    if (pos == (int)num.size())
        return rem == 0 ? 1 : 0;
    // ...
    for (int d = 0; d <= lim; d++)
        res += solve(pos + 1, tight && d == lim, (rem * 10 + d) % m);
    return memo[pos][tight][rem] = res;
}

Examples: CF 628D -- Magic Numbers, CF 914C -- Traveling Salesman and Special Numbers

---

Pattern 5: Non-Decreasing / Non-Repeating Digits

Count numbers whose digits are non-decreasing, strictly increasing, or have no repeated digits.

State: (pos, tight, last_digit) -- optionally add a started flag for leading zeros.

// Non-decreasing digits
for (int d = 0; d <= lim; d++) {
    if (!started || d >= last)
        res += solve(pos + 1, tight && d == lim, d, started || d > 0);
}

Examples: CF 1073E -- Segment of Palindromes, CF 1245F -- Daniel and Spring Cleaning

---

Pattern 6: Digit DP with Two Bounds Simultaneously

Some problems need to count pairs $(a,b)$ where $a\in [0,A]$ and $b\in [0,B]$ with a joint property (e.g., $a\oplus b\le C$). Track two tight flags simultaneously.

State: (pos, tight_a, tight_b, ...)

Examples: CF 1245F -- Daniel and Spring Cleaning, CF 276D -- Little Girl and Maximum XOR

---

Pattern 7: Digit DP in Non-Decimal Bases

Same idea, but digits range from $0$ to $\text{base}-1$. Convert $N$ to the target base first.

Trick: For binary, the tight constraint means the current bit is $\le$ the corresponding bit of $N$.

// Convert N to binary digits
vector<int> bits;
while (N > 0) { bits.push_back(N & 1); N >>= 1; }
reverse(bits.begin(), bits.end());

Examples: CF 855E -- Salazar Slytherin's Locket

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                      DIGIT DP CHEAT SHEET                        |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - "Count numbers in [L, R] with digit property P"             |
|   - N up to 10^18 (can't iterate)                                |
|   - Property depends on individual digits                        |
+------------------------------------------------------------------+
| CORE IDEA:                                                       |
|   solve(pos, tight, state)                                       |
|   - pos: current digit index (MSD first)                         |
|   - tight: are we still bounded by N?                            |
|   - state: problem-specific (digit sum, remainder, etc.)         |
|   - Range [L,R]: f(R) - f(L-1)                                  |
+------------------------------------------------------------------+
| TEMPLATE:                                                        |
|   string num = to_string(N);                                     |
|   int lim = tight ? (num[pos]-'0') : 9;                         |
|   for (int d = 0; d <= lim; d++)                                 |
|     res += solve(pos+1, tight && d==lim, new_state);             |
+------------------------------------------------------------------+
| COMPLEXITY: O(digits * 10 * |state|)    typically < 10^5         |
| SPACE: O(digits * |state|)                                       |
+------------------------------------------------------------------+
| GOTCHAS: leading zeros, tight propagation, f(L-1) when L=0      |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Leading Zeros

If the property cares about leading zeros (e.g., "count of digit 0" or "digits are non-decreasing"), you need a started flag. A number like 007 is really 7 -- the leading zeros aren't part of the number.

// Add 'started' parameter: true once a non-zero digit is placed
long long solve(int pos, bool tight, int state, bool started) {
    // ...
    for (int d = 0; d <= lim; d++) {
        bool new_started = started || (d > 0);
        int new_state = new_started ? update(state, d) : state;
        res += solve(pos + 1, tight && d == lim, new_state, new_started);
    }
}

Without this, you'll over-count zeros or produce wrong results for monotonicity constraints.

Diagram: Leading Zeros Branching

LEADING ZEROS -- counting "no repeated consecutive digits" for N = 102

                     solve(pos=0, started=false)
                    /            |             \
                d=0              d=1            ...
              started=F       started=T
           (still leading)  (real digit!)
            /       \          /       \
        d=0       d=1..9    d=0      d=1
     started=F  started=T    ↓        ↓
    (still "0")  (now "1X") last=0   last=1
         ↓        check     prev!=0?  prev!=1?
     continues... prev!=cur   yes OK    yes OK

  WHY IT MATTERS:
  ┌──────────────────────────────────────────────────────┐
  │ Without started flag:  "007" -> digits 0,0,7          │
  │   -> Two consecutive 0s! Flagged as "repeated" X      │
  │                                                      │
  │ With started flag:     "007" is really just "7"      │
  │   -> Single digit, no consecutive pair. Valid OK       │
  │                                                      │
  │ Rule: Don't apply the digit property until           │
  │       started=true (a non-zero digit has appeared).  │
  └──────────────────────────────────────────────────────┘

Tight Flag in Memoization Key

The tight flag MUST be part of the memoization key. dp[pos][sum] is WRONG if it ignores whether we're still constrained by the upper bound. The correct state is dp[pos][sum][tight]. Without tight in the key, you'll cache a "tight" result and reuse it in an "untight" context (or vice versa), producing wrong counts.

  Upper bound: 345
  At position 1, digit = 3 (tight): next digit can be 0-4
  At position 1, digit = 2 (not tight): next digit can be 0-9

  If you memoize dp[1][sum] without tight, you'll return the tight answer
  for the untight case (or vice versa) -- wrong count.

Tight Flag Propagation

The tight flag propagates as tight && (d == lim). If the current digit is strictly less than $N$'s digit at this position, all subsequent positions are free. If you write tight && (d <= lim) -- that's always tight, which is wrong.

$[L,R]$ Decomposition Edge Cases

• $L=0$: $f(L-1)=f(-1)$. Return 0 for negative inputs.
• $L=1$: $f(0)$ should count the number 0 if it satisfies the property.
• Off-by-one: double-check whether your count(N) includes $N$ itself (it should).

Memo Table Size

For $N\le {10}^{18}$: at most 19 digits. Digit sum can be at most $9\times 18=162$. Remainder mod $m$ has $m$ values. Compute the state space before coding -- if it exceeds $\sim {10}^7$, reconsider the state.

Using memset Correctly

memset(memo, -1, sizeof memo) sets every byte to 0xFF. For long long, this makes every entry $-1$ (two's complement). This is a standard trick -- it works reliably on all competitive programming judges. But if you use int arrays, same applies. Don't use memset with values other than $0$ or $-1$.

Debugging Checklist

1. Print the digit string -- verify to_string(N) gives what you expect.
2. Test $f(0)$: should return 1 if the number 0 satisfies the property, else 0.
3. Test small cases by brute force: loop $0$ to $100$, compare with count(100).
4. Check memo dimensions: pos up to 19, tight is 0/1, state varies.
5. Verify sum > K pruning (or equivalent) -- without it, TLE on large states.

Mental Traps

Trap 1: "The tight flag only matters for the first digit."

Wrong. The tight flag propagates through every digit position. It starts true and stays true only as long as every digit placed so far exactly matches $N$'s prefix. The moment you place a digit below $N$'s corresponding digit, tight becomes false and remains false for all subsequent positions. It's not a one-shot check -- it's a running constraint.

  N = 4728.  Placing digits left to right:

  pos=0: d=4  tight=T -> T  (matched N[0]=4, still bounded)
  pos=1: d=7  tight=T -> T  (matched N[1]=7, still bounded)
  pos=2: d=1  tight=T -> F  (1 < N[2]=2, FREED! never tight again)
  pos=3: d=?  tight=F -> F  (free: can place 0..9 regardless)

  vs.

  pos=0: d=4  tight=T -> T
  pos=1: d=7  tight=T -> T
  pos=2: d=2  tight=T -> T  (matched N[2]=2, still bounded)
  pos=3: d=?  tight=T -> ?  (bounded: can only place 0..N[3]=8)

  ┌──────────────────────────────────────────────────┐
  │  tight propagates as: tight && (d == N[pos])     │
  │  Once false, it NEVER becomes true again.        │
  └──────────────────────────────────────────────────┘

Trap 2: "Leading zeros don't matter."

They absolutely do for structural digit properties. Consider "count numbers with no repeated digits." If you treat 007 as having digits $[0,0,7]$, you see two consecutive 0s and reject it -- but the number 7 has no repeated digits and should be counted. Any property that examines relationships between digits (consecutive, monotonicity, uniqueness) is corrupted by phantom leading zeros. Always ask: "Would my property give a different answer for 00...0X vs X?" If yes, add a started flag.

Trap 3: "I can just iterate from L to R."

That's $O(R-L)$ time. When $R={10}^{18}$ and $L=1$, that's ${10}^{18}$ iterations -- roughly 30 years at ${10}^9$ ops/sec. Digit DP does it in $O(\text{digits}\times \text{states}\times 10)$, which is typically under ${10}^5$. The key insight: you're not examining each number -- you're counting how many numbers can be built under constraints.

  Brute force:  for x in [1, 10^18]: if property(x): count++
                -> 10^18 iterations.  IMPOSSIBLE.

  Digit DP:     solve(pos, tight, state) with memoization
                -> 18 positions x |state| x 10 digits
                -> typically 10^4 to 10^5.  INSTANT.

  +------------------------------------------------------+
  | The trick: don't enumerate numbers.                  |
  | Enumerate CONSTRAINED DIGIT SEQUENCES and count      |
  | how many valid completions each partial sequence has. |
  +------------------------------------------------------+

---

Common Mistakes

1. Omitting tight from the memo key. Memoizing on (pos, remainder) alone: when tight = true, digits at pos are restricted to [0, s[pos]]; when tight = false, they range over [0, 9]. Caching without distinguishing these reuses a cached "free" result for a "tight" context (or vice versa), producing overcounts. Every flag that affects the set of legal transitions must be part of the memoization key.
2. Missing leading_zero / started flag on structural properties. If the property examines relationships between digits (consecutive-equal, monotonicity, uniqueness), "007" treated as [0, 0, 7] gives a different answer than "7". Any property that is corrupted by phantom leading zeros needs a started flag.
3. Prefix subtraction off-by-one. countUpTo(R) - countUpTo(L) excludes L itself; use countUpTo(R) - countUpTo(L-1). For string-encoded bounds, implement subtract_one(string) with borrow handling.
4. Tight flag propagation bug. The correct propagation is tight && (d == lim). Writing tight && (d <= lim) keeps you tight forever.
5. f(-1) when L = 0. Return 0 for negative inputs -- the decomposition breaks otherwise.

Debug Drills

Drill 1. Leading zeros miscounted.

// Count numbers in [1, N] with no two adjacent equal digits
// N given as string s
int dp[20][10][2]; // [pos][last_digit][tight]
string s;

int solve(int pos, int last, bool tight) {
    if (pos == s.size()) return 1;
    if (dp[pos][last][tight] != -1) return dp[pos][last][tight];
    int lim = tight ? s[pos] - '0' : 9;
    int res = 0;
    for (int d = 0; d <= lim; d++) {
        if (d == last) continue; // no two adjacent equal
        res += solve(pos + 1, d, tight && (d == lim));
    }
    return dp[pos][last][tight] = res;
}
// Called as: solve(0, -1, true)  -- but last=-1 is used as array index!

What's wrong?

Two bugs: (1) last = -1 is used as an array index, causing undefined behavior. (2) Without a leading_zero flag, the number "007" is treated as having the digit sequence 0->0->7, which incorrectly triggers the "no adjacent equal" rejection (the two leading 0s). Fix: Add a started boolean to the state. When started = false, don't enforce the adjacency constraint, and don't record d = 0 as last. Use last = 10 (a sentinel) when no digit has been placed yet.

Drill 2. Prefix subtraction off by one.

// Count numbers in [L, R] divisible by 13
long long countUpTo(string n) {
    // ... digit DP returning count of x in [0, n] with x % 13 == 0
}

int main() {
    string L, R;
    cin >> L >> R;
    // BUG: should be countUpTo(R) - countUpTo(L-1)
    cout << countUpTo(R) - countUpTo(L) << endl;
}

What's wrong?

countUpTo(R) - countUpTo(L) excludes L itself from the count. If L is divisible by 13, it won't be counted. Fix: Compute countUpTo(R) - countUpTo(L-1). Since L is a string, implement a subtract_one(string) helper that decrements the number-as-string, handling borrow (e.g., "1000" -> "999"). Alternatively, define countUpTo to count [1, n] and adjust: countUpTo(R) - countUpTo(L) + (L % 13 == 0).

Drill 3. Memoization includes too few states.

// Count numbers in [0, N] where digit sum == target
map<pair<int,int>, long long> memo; // (pos, current_sum)
string s;

long long solve(int pos, int sum, bool tight) {
    if (pos == s.size()) return sum == target;
    auto key = make_pair(pos, sum);
    if (memo.count(key)) return memo[key]; // BUG: ignores tight!
    int lim = tight ? s[pos] - '0' : 9;
    long long res = 0;
    for (int d = 0; d <= lim; d++)
        res += solve(pos + 1, sum + d, tight && (d == lim));
    return memo[key] = res;
}

What's wrong?

The memo key is (pos, sum) but the result depends on tight. When tight = true, the digit range is [0, s[pos]-'0']; when tight = false, it's [0, 9]. Caching without tight means a "restricted" result can be returned for an "unrestricted" call (or vice versa). Fix: Include tight in the key: auto key = make_tuple(pos, sum, tight);. A common optimization: only memoize when tight = false, since the tight path is visited at most once (one unique prefix matches the bound exactly).

---

Self-Test

Before moving to practice problems, verify you can handle these without looking at the template:

• [ ] Explain what the "tight" flag means and why it's needed in digit DP. What goes wrong if you omit it from the memoization key?
• [ ] Implement a function that counts numbers in $[L,R]$ with digit sum exactly $S$ using digit DP. Handle the $L=0$ edge case.
• [ ] Handle the leading zeros case correctly for the "no repeated consecutive digits" problem -- explain where the started flag goes and how it changes the state transitions.
• [ ] Use the $f(R)-f(L-1)$ decomposition to convert a range query into two prefix queries. Explain why this works and when it could fail.
• [ ] State the time complexity of digit DP: $O(\text{digits}\times \text{states}\times 10)$ where digits $\approx 18$ for $N\le {10}^{18}$.
• [ ] Debug scenario: your digit DP counts 0 as a valid number when it shouldn't -- identify where the bug is. (Hint: check your base case and whether started matters for your property.)

---

Practice Problems

CF Rating	What You Should Be Comfortable With
1200	Understand the tight flag; solve "count numbers up to N with digit sum = S" by hand; write the basic recursive + memoization template
1500	Handle [L, R] via prefix subtraction; add a leading_zero flag; solve problems where the property involves adjacent digits (e.g., no two equal adjacent digits)
1800	Combine digit DP with divisibility states (remainder mod M); handle multiple simultaneous constraints; solve CF 628D (Magic Numbers) and CSES Counting Numbers
2100	Two-number digit DP (pair enumeration); non-decimal bases; digit DP on very large numbers given as strings; optimizations for large moduli or state spaces

#	Problem	Source	Difficulty	Key Idea
1	Classy Numbers	CF 1036C	1700	Digit sum $\le 3$; canonical digit DP warmup
2	Magic Numbers	CF 628D	1800	Divisibility + forbidden digit positions
3	Daniel and Spring Cleaning	CF 1245F	1800	Count pairs with $a+b=a\oplus b$; two-bound digit DP
4	Traveling Salesman and Special Numbers	CF 914C	1800	Binary digit DP + steps to reach 1
5	Salazar Slytherin's Locket	CF 855E	1900	Multi-base digit DP, equal 0s and 1s
6	Beautiful Numbers	CF 55D	2000	Number divisible by all its digits; LCM state
7	Investigation	LightOJ 1068	1900	Digit sum + divisibility combined
8	Numbers At Most N Given Digit Set	LC 902	1700	Restricted digit set; simpler variant
9	Segment of Palindromes	CF 1073E	2100	Digit DP on multiple numbers simultaneously
10	Little Girl and Maximum XOR	CF 276D	1700	Binary digit DP / bit analysis
11	Counting Numbers	CSES	1700	Count integers in [a,b] with no two adjacent digits equal

---

Further Reading

• cp-algorithms: Digit DP -- clean writeup with multiple examples.
• CF Blog: Digit DP introduction -- community tutorial with practice problems.
• CF Blog: Everything about Digit DP -- detailed patterns and tricks.
• Prerequisite: DP -- 1D Introduction
• Related: DP -- Bitmask, DP -- Interval

---