DP chữ số (Digit DP)

Wiki › Thuật toán › Quy hoạch động (DP)

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

DP chữ số (Digit DP) là kỹ thuật quy hoạch động dùng để đếm số lượng số nguyên trong đoạn $[L, R]$ thỏa mãn một tính chất nào đó liên quan đến các chữ số của số đó.

Khi nào dùng Digit DP?

Dấu hiệu nhận biết bài toán Digit DP:

Đếm số nguyên trong $[L, R]$ (hoặc $[1, N]$ ) thỏa mãn điều kiện.
Điều kiện phụ thuộc vào từng chữ số của số đó (tổng chữ số, số chữ số lẻ, không có hai chữ số liền nhau bằng nhau, ...).
$N$ rất lớn (lên tới $10^{18}$ ), không thể duyệt trâu.

Ý tưởng cốt lõi: Xây số từ chữ số cao nhất xuống thấp nhất, dùng DP để đếm.

Kỹ thuật nền tảng: $f (N)$

Thay vì đếm trên $[L, R]$ , ta quy về:

Đáp án = f (R) - f (L - 1)

trong đó $f (N)$ = số lượng số trong $[0, N]$ thỏa mãn điều kiện.

Mô hình trạng thái chung

Khi xây số từng chữ số (từ trái sang phải), ta theo dõi:

Tham số	Ý nghĩa
`pos`	Đang chọn chữ số thứ mấy (từ 0)
`tight`	Có đang bị ràng buộc bởi giới hạn trên không?
`...state...`	Trạng thái bài toán cụ thể (tổng chữ số, chữ số cuối, ...)

Nếu tight = true: chữ số tiếp theo chỉ được chọn từ 0 đến digits[pos].
Nếu tight = false: chữ số tiếp theo được chọn tự do từ 0 đến 9.

Ví dụ 1: Đếm số có tổng chữ số bằng $S$ trong $[0, N]$

Định nghĩa DP

dp[pos][sum][tight]
= số lượng cách hoàn thành số từ vị trí pos
  sao cho tổng chữ số phần còn lại đúng bằng (S - sum)

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

int S;
string digits;
int memo[20][200][2];

// Trả về số lượng số hợp lệ từ vị trí pos
int dp(int pos, int sum, bool tight) {
    if (sum > S) return 0;
    if (pos == (int)digits.size()) return sum == S ? 1 : 0;

    int& ret = memo[pos][sum][tight];
    if (ret != -1) return ret;

    int limit = tight ? (digits[pos] - '0') : 9;
    ret = 0;
    for (int d = 0; d <= limit; d++) {
        ret += dp(pos + 1, sum + d, tight && d == limit);
    }
    return ret;
}

// Đếm số trong [0, N] có tổng chữ số = S
int f(long long N) {
    digits = to_string(N);
    memset(memo, -1, sizeof(memo));
    return dp(0, 0, true);
}

int main() {
    long long L, R;
    cin >> L >> R >> S;
    cout << f(R) - f(L - 1) << "\n";
}

Ví dụ 2: Đếm số không có hai chữ số liền nhau bằng nhau

Trạng thái

dp(pos, lastDigit, tight)

lastDigit: chữ số vừa chọn ở vị trí trước.

#include <bits/stdc++.h>
using namespace std;

string digits;
int memo[20][10][2];

int dp(int pos, int last, bool tight) {
    if (pos == (int)digits.size()) return 1;

    int& ret = memo[pos][last][tight];
    if (ret != -1) return ret;

    int limit = tight ? (digits[pos] - '0') : 9;
    ret = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == last) continue; // không chọn chữ số trùng với trước
        ret += dp(pos + 1, d, tight && d == limit);
    }
    return ret;
}

int f(long long N) {
    if (N < 0) return 0;
    digits = to_string(N);
    memset(memo, -1, sizeof(memo));
    // last = -1 (không có chữ số nào trước)
    // Xử lý: cho phép tất cả chữ số ở vị trí đầu
    int limit = digits[0] - '0';
    int ans = 0;
    for (int d = 0; d <= limit; d++) {
        memset(memo, -1, sizeof(memo));
        ans += dp(1, d, d == limit);
    }
    return ans;
}

Lưu ý: Số 0 thường được xử lý riêng hoặc dùng thêm cờ started để đánh dấu đã bắt đầu điền chữ số khác 0 chưa (tránh đếm số 007 là số 3 chữ số).

Xử lý số 0 đứng đầu (Leading Zeros)

Nhiều bài cần phân biệt số 007 (7 chữ số) với 7 (1 chữ số). Thêm tham số started:

int dp(int pos, int state, bool tight, bool started) {
    if (pos == n) return started ? (state == target) : 0;

    int& ret = memo[pos][state][tight][started];
    if (ret != -1) return ret;

    int limit = tight ? (digits[pos] - '0') : 9;
    ret = 0;
    for (int d = 0; d <= limit; d++) {
        bool newStarted = started || (d != 0);
        // Nếu chưa started và d = 0: vẫn là số 0 đứng đầu
        int newState = newStarted ? transition(state, d) : state;
        ret += dp(pos + 1, newState, tight && d == limit, newStarted);
    }
    return ret;
}

Cấu trúc tổng quát (Template)

#include <bits/stdc++.h>
using namespace std;

string digits;
// memo[pos][...trạng_thái...][tight][started]
// Kích thước tùy bài

long long dp(int pos, /* trạng thái */, bool tight, bool started) {
    // Base case
    if (pos == (int)digits.size()) {
        return started && /* điều kiện thỏa */ ? 1 : 0;
    }

    // Kiểm tra memo
    // ...

    int limit = tight ? (digits[pos] - '0') : 9;
    long long ret = 0;

    for (int d = 0; d <= limit; d++) {
        bool newStarted = started || (d != 0);
        bool newTight = tight && (d == limit);
        // Cập nhật trạng thái
        ret += dp(pos + 1, /* trạng thái mới */, newTight, newStarted);
    }

    // Lưu memo và trả về
    return ret;
}

long long f(long long N) {
    if (N < 0) return 0;
    digits = to_string(N);
    // Xóa memo
    return dp(0, /* trạng thái ban đầu */, true, false);
}

int main() {
    long long L, R;
    cin >> L >> R;
    cout << f(R) - f(L - 1) << "\n";
}

Độ phức tạp

	Độ phức tạp
Thời gian	$O (\log N \times ‖ S ‖ \times 10)$
Không gian	$O (\log N \times ‖ S ‖)$

Trong đó $‖ S ‖$ là kích thước không gian trạng thái bài toán.

Với $N \leq 10^{18}$ , $\log N \approx 18$ chữ số → rất nhanh.

Các dạng bài thường gặp

Bài toán	Trạng thái cần theo dõi
Tổng chữ số bằng $S$	`sum`
Tổng chữ số chia hết cho $K$	`sum % K`
Số lần xuất hiện của chữ số $d$	`count`
Không có hai chữ số liền nhau bằng nhau	`lastDigit`
Số chữ số lẻ = số chữ số chẵn	`diff = odd - even`
Số là bội của $K$	`value % K`
Không chứa chữ số $d$ nào	(lọc ngay trong vòng lặp)

Mẹo & Lưu ý

Memoization vs Tabulation: Với Digit DP, đệ quy + memo thường dễ cài hơn.
Xóa memo trước mỗi lần gọi f(N): Tham số tight ảnh hưởng đến kết quả — nếu tái sử dụng memo giữa f(R) và f(L-1) sẽ sai.
Kiểu dữ liệu: Kết quả có thể rất lớn, dùng long long hoặc lấy modulo nếu đề yêu cầu.
Trường hợp $L = 0$ : Xử lý cẩn thận f(L - 1) = f(-1) = 0.

Bài tập luyện tập

Đếm số trong $[L, R]$ có tổng chữ số chia hết cho $K$ .
Đếm số "may mắn" (chỉ chứa chữ số 4 và 7) trong $[L, R]$ .
Đếm số trong $[L, R]$ không chứa hai chữ số $i$ và $j$ liền nhau.
Đếm số trong $[1, N]$ mà giá trị của số bằng tổng giai thừa các chữ số (số Armstrong).

Bình luận

Không có bình luận tại thời điểm này.