When solving counting problems over large numerical ranges, traditional anumeration becomes inefficient due to redundant computations. Consider counting processes from 7000 to 7999, 8000 to 8999, and 9000 to 9999. These intervals share a common pattern: the lower three digits cycle from 000 to 999, with only the thousand's digit varying. This observation forms the foundation of digit dynamic programming—we can consolidate these similar processes and store intermediate results in a state array, enabling efficient computation through memoization or iterative DP.

The state definition varies based on problem requirements. The general approach involves processing digits from the most significant position to the least significant, determining valid digit choices at each position, and leveraging precomputed results to avoid recalculating overlapping subproblems.

Example 1: Counting Numbers with K Ones in Binary

Given a integer N, count how many integers from 1 to N contain exactly K ones in their binary representation. Constraints: 1 ≤ N ≤ 10^18, 1 ≤ K ≤ 50.

Walkthrough for N=7 (binary 111) and K=2:

• Starting from the highest bit, choosing 0 creates pattern 0__. The maximum value 011 doesn't exceed our limit, so we add C(2, 2) combinations for the remaining two positions.
• Choosing 1 creates pattern 1__, and we track the running count of ones.
• For the second bit: choosing 0 gives 10_, adding C(1, 1) combinations. Choosing 1 increments the one count.
• For the final bit at 11_, we have 2 ones which equals K, contributing 1 to the answer.

Result: C(2, 2) + C(1, 1) + 1 = 3

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ULL;

const int MAX_BITS = 64;
ULL combinations[MAX_BITS][MAX_BITS];

void initCombinations() {
    for (int i = 0; i < MAX_BITS; i++) {
        combinations[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            combinations[i][j] = combinations[i-1][j-1] + combinations[i-1][j];
        }
    }
}

int main() {
    initCombinations();
    
    ULL n, targetOnes;
    cin >> n >> targetOnes;
    
    vector<int> bitArray;
    ULL temp = n;
    while (temp > 0) {
        bitArray.push_back(temp & 1);
        temp >>= 1;
    }
    
    ULL answer = 0;
    int onesSoFar = 0;
    int totalBits = bitArray.size();
    
    for (int i = totalBits - 1; i >= 0; i--) {
        if (i == 0) {
            if (onesSoFar == targetOnes || onesSoFar + bitArray[i] == targetOnes) {
                answer++;
            }
        } else if (bitArray[i] == 1) {
            int remainingPositions = i;
            int neededOnes = targetOnes - onesSoFar;
            if (neededOnes >= 0 && neededOnes <= remainingPositions) {
                answer += combinations[remainingPositions][neededOnes];
            }
            onesSoFar++;
        }
    }
    
    cout << answer << endl;
    return 0;
}

Example 2: Digit Frequency Count in Range [a, b]

Given two positive integers a and b, calculate the total occurrences of each digit (0-9) across all integers in the range [a, b].

Iterative Implementation

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

const int MAX_LEN = 14;
LL accumulated[MAX_LEN];

void computeDigitFrequency(LL bound, LL frequency[]) {
    if (bound <= 0) return;
    
    vector<int> digits;
    LL temp = bound;
    do {
        digits.push_back(temp % 10);
        temp /= 10;
    } while (temp > 0);
    
    int len = digits.size();
    LL remaining = bound;
    
    for (int pos = len; pos >= 1; pos--) {
        int currentDigit = digits[pos - 1];
        
        for (int d = 0; d < 10; d++) {
            frequency[d] += accumulated[pos - 1] * currentDigit;
        }
        
        LL powerVal = pow(10.0, pos - 1);
        for (int d = 0; d < currentDigit; d++) {
            frequency[d] += powerVal;
        }
        
        remaining -= powerVal * currentDigit;
        frequency[currentDigit] += remaining + 1;
        
        if (pos > 1) {
            frequency[0] -= powerVal;
        }
    }
}

int main() {
    for (int i = 1; i < MAX_LEN; i++) {
        accumulated[i] = 10 * accumulated[i-1] + pow(10.0, i-1);
    }
    
    LL a, b;
    cin >> a >> b;
    
    LL freqA[10] = {0}, freqB[10] = {0};
    computeDigitFrequency(a - 1, freqA);
    computeDigitFrequency(b, freqB);
    
    for (int i = 0; i < 10; i++) {
        if (i > 0) cout << " ";
        cout << freqB[i] - freqA[i];
    }
    cout << endl;
    
    return 0;
}

Recursive Implementation

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAX_LEN = 14;
LL powers[MAX_LEN], digitPrefix[MAX_LEN];

int countDigits(LL num) {
    int cnt = 0;
    do {
        cnt++;
        num /= 10;
    } while (num > 0);
    return cnt;
}

void countRecursive(LL num, int depth, LL result[]) {
    if (depth == 0) return;
    
    int topDigit = num / powers[depth - 1] % 10;
    
    for (int d = 0; d < topDigit; d++) {
        result[d] += powers[depth - 1];
    }
    
    for (int d = 0; d < 10; d++) {
        result[d] += digitPrefix[depth - 1] * topDigit;
    }
    
    LL remainder = num - topDigit * powers[depth - 1];
    result[topDigit] += remainder + 1;
    result[0] -= powers[depth - 1];
    
    countRecursive(remainder, depth - 1, result);
}

int main() {
    powers[0] = 1;
    for (int i = 1; i < MAX_LEN; i++) {
        powers[i] = powers[i-1] * 10;
        digitPrefix[i] = digitPrefix[i-1] * 10 + powers[i-1];
    }
    
    LL a, b;
    cin >> a >> b;
    
    LL resultA[10] = {0}, resultB[10] = {0};
    countRecursive(a - 1, countDigits(a - 1), resultA);
    countRecursive(b, countDigits(b), resultB);
    
    for (int i = 0; i < 10; i++) {
        if (i > 0) cout << " ";
        cout << resultB[i] - resultA[i];
    }
    cout << endl;
    
    return 0;
}