Digit Dynamic Programming evaluates the count of numbers in a range $[L, R]$ satisfying complex positional, parity, or digit-frequency constraints. The standard technique transforms the range into $f(R) - f(L - 1)$ using prefix subtraction.
1. Canonical Digit DP State Tuple
long long dfs(int idx, bool is_tight, bool is_leading_zero, int mask) {
if (idx == digits.size()) return 1; // Valid number constructed
if (!is_tight && !is_leading_zero && memo[idx][mask] != -1)
return memo[idx][mask];
int limit = is_tight ? digits[idx] : 9;
long long total = 0;
for (int d = 0; d <= limit; ++d) {
bool next_tight = is_tight && (d == limit);
bool next_lz = is_leading_zero && (d == 0);
int next_mask = next_lz ? 0 : (mask | (1 << d));
total += dfs(idx + 1, next_tight, next_lz, next_mask);
}
if (!is_tight && !is_leading_zero)
memo[idx][mask] = total;
return total;
}