Kỹ thuật số位 DP giải quyết bài toán đếm số thỏa mãn điều kiện trong khoảng [L, R] thông qua việc xử lý từng chữ số. Mô hình trạng thái thường có dạng dp[length][firstDigit][target], với length là độ dài số, firstDigit là chữ số đầu tiên, target là giá trị cần đếm.

Bài toán minh họa: Đếm tần suất chữ số (P2602)
Xây dựng mảng digitCount với digitCount[len][start][target] lưu số lượng số có độ dài len, chữ số đầu start, chứa target lần lượt. Quá trình tiền xử lý:

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

ll digitCount[14][10][10];

ll calculateCount(ll bound, int target) {
    int digits[15] = {}, len = 0;
    ll total = 0;
    
    // Tách chữ số theo thứ tự ngược
    while (bound) {
        digits[++len] = bound % 10;
        bound /= 10;
    }
    
    // Tính số với độ dài nhỏ hơn
    for (int l = 1; l < len; l++) {
        for (int start = 1; start <= 9; start++) {
            total += digitCount[l][start][target];
        }
    }
    
    // Xử lý số cùng độ dài
    for (int start = 1; start < digits[len]; start++) {
        total += digitCount[len][start][target];
    }
    
    for (int pos = len - 1; pos >= 1; pos--) {
        for (int d = 0; d < digits[pos]; d++) {
            total += digitCount[pos][d][target];
        }
        if (abs(digits[pos + 1] - target) < 2) break;
    }
    return total;
}

int main() {
    // Tiền xử lý digitCount
    for (int d = 0; d <= 9; d++) 
        digitCount[1][d][d] = 1;
    
    for (int len = 2; len <= 13; len++) {
        for (int start = 0; start <= 9; start++) {
            for (int prev = 0; prev <= 9; prev++) {
                for (int t = 0; t <= 9; t++) {
                    digitCount[len][start][t] += digitCount[len - 1][prev][t];
                }
            }
            digitCount[len][start][start] += pow(10, len - 1);
        }
    }
    
    ll A, B;
    cin >> A >> B;
    for (int num = 0; num <= 9; num++) {
        cout << calculateCount(B + 1, num) - calculateCount(A, num) << " ";
    }
    return 0;
}

Bài toán Windy Numbers (P2657)
Áp dụng mô hình tương tự với trạng thái windyCount[len][start] đếm số Windy có độ dài len, chữ số đầu start. Điều kiện: |chữ số liền kề| ≥ 2.

#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;

ll windyCount[11][10];
int digitSeq[11];

ll countWindy(ll upper) {
    int len = 0;
    ll result = 0;
    
    // Chuẩn bị dãy chữ số
    while (upper) {
        digitSeq[++len] = upper % 10;
        upper /= 10;
    }
    
    // Tổng số có độ dài nhỏ hơn
    for (int l = 1; l < len; l++) {
        for (int start = 1; start <= 9; start++) {
            result += windyCount[l][start];
        }
    }
    
    // Xử lý số cùng độ dài
    for (int start = 1; start < digitSeq[len]; start++) {
        result += windyCount[len][start];
    }
    
    for (int pos = len - 1; pos >= 1; pos--) {
        for (int d = 0; d < digitSeq[pos]; d++) {
            if (abs(d - digitSeq[pos + 1]) >= 2) {
                result += windyCount[pos][d];
            }
        }
        if (abs(digitSeq[pos] - digitSeq[pos + 1]) < 2) break;
    }
    return result;
}

int main() {
    // Tiền xử lý windyCount
    for (int d = 0; d <= 9; d++) 
        windyCount[1][d] = 1;
    
    for (int len = 2; len <= 10; len++) {
        for (int start = 0; start <= 9; start++) {
            for (int prev = 0; prev <= 9; prev++) {
                if (abs(start - prev) >= 2) {
                    windyCount[len][start] += windyCount[len - 1][prev];
                }
            }
        }
    }
    
    ll L, R;
    cin >> L >> R;
    cout << countWindy(R) - countWindy(L - 1);
    return 0;
}