DP Digit - Quy hoạch động chữ số

Mục lục

Phần 1: Giới thiệu về DP Digit

DP Digit (hay được biết đến là Quy hoạch động chữ số) là một kỹ thuật dùng để giải các bài toán đếm hoặc tính toán liên quan đến số nguyên rất lớn, thông qua việc xử lý từng chữ số của số đó theo quy hoạch động.

Khi nào thì sử dụng DP Digit?

Khi bạn cần đếm hoặc tính số lượng số trong một khoảng nhất đinh thoả mãn một số điều kiện mà đề bài cho. Chẳng hạn như tổng của chúng bằng N, chữ số đầu gấp 3 lần chữ số cuối,…
Giới hạn khoảng cách rất lớn, có thể lên tới 1e18 nên nếu chỉ tính duyệt từng số thôi là bất khả thi.

1.1 Bài toán ví dụ về DP Digit

Yêu cầu: Đếm tất cả số từ 1 đến 1000 có tổng các chữ số bằng 10.

Ví dụ:

Số 109 (1 + 0 + 9 = 10) → Hợp lệ.
Số 55 (5 + 5 = 10) → Hợp lệ.
Số 123 (1 + 2 + 3 = 6) → Không hợp lệ.

1.2 Cách làm “ngây thơ” và vấn đề

Cách làm thông thường: Duyệt từng số từ 1 đến 1000, tính tổng chữ số và kiểm tra.

Vấn đề: Nếu số lớn đến hàng tỷ (ví dụ: 1e18), cách này quá chậm!

→ Cần một phương pháp thông minh hơn: DP Digit!

Phần 2: Tư tưởng chính của DP Digit

2.1 Phân rã số thành các chữ số

Ví dụ: Số 314 → phân tích thành các chữ số [3, 1, 4].

Xử lý từng chữ số một từ trái sang phải.

2.2 Quy tắc “ràng buộc” (tight)

Khi xây dựng số, nếu các chữ số trước đó giống hệt số gốc, chữ số tiếp theo không được vượt quá chữ số tương ứng của số gốc.

Ví dụ: Xét số gốc 314:

Nếu 2 chữ số đầu là 3 và 1 → Chữ số thứ 3 tối đa là 4.
Nếu chữ số đầu là 2 → Chữ số thứ 2 có thể từ 0 đến 9.

2.3 Trạng thái DP

Khi xử lý đến chữ số thứ pos, ta cần lưu:

Tổng các chữ số đã chọn (sum).
Trạng thái ràng buộc (tight): Có đang bị giới hạn bởi số gốc?
Đã bắt đầu số (started): Phân biệt số 0 (0 không tính là số đã bắt đầu).

Phần 3: Code C++ DP Digit minh hoạ

Bài toán: Tìm số lượng số có tổng các chữ số bằng X

3.1 Code mẫu

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

string number; // Lưu số dưới dạng chuỗi (ví dụ: "1234")
int target = 10; // Tổng chữ số cần đạt
int memo[20][200][2][2]; // Bộ nhớ đệm

// pos: Vị trí chữ số hiện tại (0 → độ dài số - 1)
// sum: Tổng chữ số đã chọn
// tight: Có đang bị ràng buộc bởi số gốc?
// started: Số đã bắt đầu (bỏ qua số 0 đầu)
int dp(int pos, int sum, bool tight, bool started) {
    // Kết thúc xử lý tất cả chữ số
    if (pos == number.size()) {
        return (sum == target && started) ? 1 : 0;
    }
    
    // Kiểm tra bộ nhớ đệm
    if (memo[pos][sum][tight][started] != -1) {
        return memo[pos][sum][tight][started];
    }
    
    // Giới hạn chữ số có thể chọn
    int limit = tight ? (number[pos] - '0') : 9;
    int count = 0;
    
    // Thử chọn từng chữ số d
    for (int d = 0; d <= limit; d++) {
        bool new_tight = tight && (d == limit);
        bool new_started = started || (d != 0);
        int new_sum = sum + (new_started ? d : 0);
        
        count += dp(pos + 1, new_sum, new_tight, new_started);
    }
    
    // Lưu kết quả vào bộ nhớ đệm
    return memo[pos][sum][tight][started] = count;
}

// Hàm đếm số từ 0 đến n thỏa mãn
int count_numbers(int n) {
    if (n < 0) return 0;
    number = to_string(n);
    memset(memo, -1, sizeof(memo));
    return dp(0, 0, true, false);
}

int main() {
    int L = 1, R = 1000;
    int result = count_numbers(R) - count_numbers(L - 1);
    cout << "Số lượng số thỏa mãn: " << result;
}

3.2 Giải thích từng phần

Hàm dp:
- pos = 0: Bắt đầu từ chữ số đầu tiên.
- sum = 0: Tổng ban đầu bằng 0.
- tight = true: Ban đầu bị ràng buộc bởi số gốc.
- started = false: Chưa bắt đầu số (để xử lý số 0).
Xử lý chữ số d:
- Vòng lặp d: Thử chọn chữ số từ 0 đến limit.
- new_tight: Nếu trước đó tight = true và d bằng chữ số gốc → tiếp tục ràng buộc; ngược lại → không ràng buộc.
- new_started: Số bắt đầu khi chọn chữ số khác 0 đầu tiên.
- new_sum: Chỉ cộng d vào tổng nếu số đã bắt đầu.
Bộ nhớ đệm (memo): Lưu kết quả đã tính để tránh tính lại → tăng tốc độ.
Nếu bạn còn chưa chắc về phần dp cơ bản thì có thể tham khảo bài đọc sau: https://codedream.edu.vn/quy-hoach-dong-cho-nguoi-moi-bat-dau-phan-1/

Phần 4: Ví dụ DP Digit minh họa bằng tay

4.1 Ví dụ: Đếm số từ 0 đến 50 có tổng chữ số = 5

Các số hợp lệ: 5, 14, 23, 32, 41, 50.

Mô phỏng hàm dp cho số 50 (chuỗi “50”):

pos = 0:
- limit = 5 (vì tight = true).
- Chọn d = 0: new_started = false, sum vẫn = 0.
- Chọn d = 5: new_started = true, sum = 5.
pos = 1 (sau khi chọn d = 5):
- limit = 0 (vì tight = true và số gốc là 50).
- Chỉ được chọn d = 0: sum = 5 + 0 = 5 → hợp lệ.

Phần 5: Bài tập thực hành

Phần 6: Tổng kết

Sau khi tìm hiểu toàn bộ tư tưởng và cài đặt của Digit DP, chúng ta cùng nhìn lại những điểm mấu chốt và những lưu ý quan trọng khi áp dụng kỹ thuật này.

6.1 Khi nào nên dùng DP Digit

Bài toán đếm: Khi bạn cần tính xem có bao nhiêu số trong khoảng

$0, N$

hoặc

$L, R$

thoả mãn một hoặc nhiều điều kiện về chữ số (tổng chữ số, số chữ số chẵn/lẻ, không chứa chữ số nhất định, chữ số tăng/giảm, v.v.).
Bài toán tối ưu: Khi muốn tìm giá trị tối đa hoặc tối thiểu của một hàm nào đó trên chữ số (ví dụ: số nhỏ nhất có tổng chữ số bằng X, số lớn nhất không chứa chữ số 9, v.v.).
Xử lý N rất lớn: Khi N có thể lên tới 1e18 hoặc hơn, không thể lặp từng giá trị một.

6.2 4 yếu tố chính trong trạng thái DP

pos (Position)
- Chỉ số của chữ số đang xét, tính từ trái sang phải (0…len−1).
- Giúp biết chúng ta đang ở vị trí nào trong chuỗi số gốc.
sum (Accumulated Property)
- Có thể là tổng chữ số, số lượng chữ số thoả mãn, giá trị mod, hoặc bất cứ tính chất nào cần theo dõi.
- Kết quả cuối cùng phụ thuộc vào giá trị của tham số này khi pos == len.
tight (Restriction Flag)
- Xác định xem dãy chữ số đã chọn ở các vị trí trước có khớp hoàn toàn với prefix của số gốc hay không.
- Nếu tight = true, chữ số ở pos chỉ được chọn từ 0 đến chữ số gốc tại pos; nếu false, có thể chọn tự do 0–9.
started (Leading Zero Flag)
- Thường dùng để phân biệt giữa các prefix chỉ toàn chữ số 0 (chưa bắt đầu số thực) và khi chuỗi số thực sự “bắt đầu” với chữ số ≠ 0.
- Ngăn việc cộng nhầm 0 ở đầu hoặc đếm số 0 trống không.

6.3 Ưu điểm và nhược điểm của DP Digit

Ưu điểm

Hiệu suất cao: Thay vì O(N), thuật toán chạy trong O(len × S × 10) với len = số chữ số, S = kích thước không gian trạng thái (ví dụ sum tối đa), và nhân 10 cho các lựa chọn chữ số.
Linh hoạt: Dễ dàng điều chỉnh để giải hàng loạt biến thể bài toán liên quan chữ số bằng cách thêm hoặc bớt các tham số trong trạng thái.
Tái sử dụng: Cùng một khuôn mẫu DP có thể dùng cho nhiều bài toán khác nhau chỉ với vài sửa đổi nhỏ.

Nhược điểm

Cài đặt phức tạp: Khi số lượng tham số tăng, code DP dễ bị lỗi nếu không cẩn thận.
Bộ nhớ đệm lớn: Nếu sum hoặc các tham số khác có phạm vi rộng, mảng memo[...] có thể chiếm nhiều bộ nhớ.
Khó debug: Việc kiểm tra từng nhánh chữ số thủ công thường mất thời gian

6.4 Mẹo khi triển khai DP Digit

Khởi tạo memo: Dùng memset(memo, -1, sizeof memo) (C++) hoặc dp = {} (Python) để đánh dấu trạng thái chưa được tính.
Giới hạn sum: Nếu bài toán chỉ yêu cầu sum ≤ X, bạn có thể giảm kích thước mảng memo bằng cách giới hạn sum tối đa.
Bỏ qua sớm: Nếu sum đã vượt giá trị cho phép, có thể return 0 ngay mà không cần đệ quy tiếp.
Kiểm thử nhỏ: Luôn chạy thử trên các giá trị N nhỏ (như N ≤ 1000) so với cách brute-force để kiểm tra độ chính xác.