Digit DP and Counting

"How many numbers from L to R satisfy property P?" Digit DP processes the digits of the upper bound, tracking whether we've already gone smaller (tight). It's a top-down DP that counts numbers without enumerating them.

The Digit DP Pattern

State: dp[pos][tight][started] — position in the digit string, whether we're still matching the upper bound, and whether we've placed any non-zero digit yet (for leading-zero handling).

C++ — count numbers with no adjacent equal digits

string s;
vector>> memo;

long long dp(int pos, int tight, int last_digit) {
    if (pos == s.size()) return 1;

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

    int limit = tight ? s[pos] - '0' : 9;
    long long ans = 0;

    for (int d = 0; d <= limit; d++) {
        if (d == last_digit) continue;  // no adjacent equal
        ans += dp(pos + 1, tight && (d == limit), d);
    }

    return memo[pos][tight][last_digit + 1] = ans;
}

long long solve(long long n) {
    s = to_string(n);
    memo.assign(20, vector>(2, vector(11, -1)));
    return dp(0, 1, -1) - 1;  // subtract 0
}

// Range [L, R]: solve(R) - solve(L - 1)

💡 The tight flag

When tight = 1, the current digit can't exceed the bound's digit at this position. Once we place a digit smaller than the bound, tight becomes 0 for the rest of the number, and digits 0–9 are all allowed.

Key Takeaways

→ Digit DP = DP over digit positions with a tight flag.
→ Range query: solve(R) - solve(L-1).
→ Handle leading zeros with a started flag for numbers with fewer digits.

The Digit DP Pattern

C++ — count numbers with no adjacent equal digits

Key Takeaways

Practice