guest@itl:~/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
#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})