guest@cp-base:~/home/dp$
templates/digit-dp.cpp
compilable
$cat templates/digit-dp

Digit DP

Count numbers in [L, R] satisfying digit-level constraints using memoized recursion.

[Dynamic Programming]|
Jul 9, 2026
|explanatory_notes.md|
#digit-dp#dp#counting#memoization
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[20][2][2][10];
string num;

ll solve(int idx, bool tight, bool started, int last) {
    if (idx == (int)num.size())
        return started ? 1 : 0;
    ll& ret = dp[idx][tight][started][last];
    if (~ret) return ret;
    ret = 0;
    int lim = tight ? num[idx] - '0' : 9;
    for (int d = 0; d <= lim; d++) {
        bool nt = tight && (d == lim);
        bool ns = started || (d != 0);
        // add your constraint check here
        ret += solve(idx + 1, nt, ns, ns ? d : 0);
    }
    return ret;
}

ll count(ll x) {
    if (x < 0) return 0;
    num = to_string(x);
    memset(dp, -1, sizeof dp);
    return solve(0, true, false, 0);
}

ll countRange(ll l, ll r) {
    return count(r) - count(l - 1);
}
33 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Digit DP

Counts numbers in [L,R][L, R] satisfying digit-level properties without iterating every number.

Core Idea

  • Convert to: f(R)−f(L−1)f(R) - f(L-1) where f(N)f(N) counts valid numbers ≤N\le N

  • Process digits from MSB to LSB, building the number one digit at a time

    • State

  • idx — current digit position (0 = most significant)

  • tight — are all digits so far equal to NN's prefix? If true, next digit capped by N[idx]N[idx]; if false, any digit 00–99 allowed

  • started — has a nonzero digit been placed? (handles leading zeros)

  • Custom state — problem-specific (last digit, digit sum, etc.)

    • How to Adapt

  • Add dimensions to the DP array for your constraint

  • Add condition checks inside the digit loop

  • Common additions: digit sum, specific digit count, monotonicity, no-repeat constraint

    • When to Use

  • "Count numbers in [L,R][L, R] with property PP"

  • RR can be up to 101810^{18} (18 digits)

    • Complexity

  • Time — O(digits×states per position)O(\text{digits} \times \text{states per position})

  • Space — O(DP array size)O(\text{DP array size})