I) SƠ LƯỢC.
trước khi hiểu dp digit là gì, cách dp digit hoạt động thì ta phải nhìn trước xem các cấu trúc của các bài dp digit là như nào(đọc qua cấu trúc rồi sẽ giải thích khi vào bài học)

hàm qhd(idx, tight, sum, string& x)
//thcs
if idx = x.size()
	if dieu_kien: nếu đúng return 1
	return 0
//thcs 2:
nếu dp[idx][tight][sum] khác -1 thì return chính nó

fin = 0
if tight = 1: fin = x[idx]-'0'
ans = 0
for i := 0 to fin
new_idx = idx+1
new_tight
if tight = 0: new_tight = 0
if tight = 1
	if i = fin: new_tight = 1 else 0
newsum = sum+i
ans+=qhd(newidx,newtight,newsum,x)
return dp[idx][tight][sum] = ans
hàm calc(string x)
memset dp 
return dp(0,1,0,x)
cuối cùng là in ra calc(r)-calc(l)

//note, một vài bài dp digit khác có thể có cấu trúc khác một chút nhưng chung chung lại thì hầu như các bài dp digit đều như vậy, các chỗ if sẽ tự xử lí tùy theo đề bài yêu cầu

II) MAIN.
có rất nhiều dạng bài yêu cầu đếm một số x bất kì với các điều kiện phụ trong khoảng từ a -> b(ví dụ như đếm các số có tổng các chữ số là số nguyên tố từ a -> b).
và hầu hết khi nghe tới từ a -> b thì ta lại phải for, mà for là tele ngay.vì vậy nếu chúng ta nói F(x) cho biết các số nguyên như vậy nằm trong khoảng từ 1 -> x thì số nằm giữa a và b được cho bởi F(b) - F(a-1). và lúc này là lúc ta phải dùng Dp Digit
Tất cả các bài toán dạng đếm số thỏa mãn... thì đều có thể giải quyết bằng dp digit
ví dụ:
số không đẹp là các số có chứa số 5 ở trong nó, ví dụ: 15, 25, 2356, 529,...
tìm các số không đẹp từ a -> b(a <= b <= 10^18)
nếu bình thường thì ta cứ for rồi xét thôi. nhưng nhìn giới hạn thấy 10^18 là 100% dp digit rồi. hầu hết các đề bài dp digit đều như vậy cả.

1) Khái niệm chính về Dp Digit

- cho số x có n chữ số. ý tưởng chính của dp digit là phải biểu diễn các số đó ở dạng một cái string s hoặc một mảng s
giả sử chúng ta có sn sn-1 sn-2 ... s2 s1 biểu diễn dưới dạng thập phân (là chỉ có 0 và 1) trong đó si(1 <= i <= n) là số thứ i tính từ bên phải sang. chữ số ngoài cùng bên trái là sn là chữ số chính
ví dụ là:
giả sử các số có 1 chữ số, vì ở dạng string mà
vậy nên các số đó được đánh dấu từ 0 -> 8(chỉ có 9 chữ số thôi)
0 1 2 3 4 5 6 7 8
và mình sẽ cho một dãy số:
2 4 7 3 5 1 2 0 1
và cho dãy số bất kì:
1 3 _ _ _ _ _ _ _ (_ là các phần trống)
theo cấu trúc của dp, ta sẽ có 1 cái dp 3 chiều: dp[idx][tight][sum]
idx là vị trí thứ i
tight là cái số 0 hoặc 1, sum là tổng
về tight:
tiếp tục hãy nhìn lại số 1 3 mà tôi đã cho
nó ở vị trí 0 và 1
số 2 và 4 trong dãy số cũng ở vị trí 0 và 1
vì 1 < 2(vị trí đầu tiên) nên dãy chứa 1 3 đó sẽ luôn bé hơn dãy 2 4, mà bé hơn thì ta sẽ điền 0 vào tight
là dp[i][0][sum]
còn nếu dãy đó là 2 4 _ _ _ _ _ _
thì nó sẽ bằng mà nếu bằng thì sẽ điền tight = 1:
dp[i][1][sum]
i thì bây giờ i đang ở tới vị trí thứ 1 là lớn nhất, vậy lấy i=1(vẫn là dãy 1 3, 3 ở vị trí 1 thì ta lấy i=1)
dp[1][0][sum]
ta có sum = 1 + 3 = 4
thì sum = 4
dp[1][0][4]
sơ lược là vậy, phần này mình giảng sơ qua để tí code cho dễ hiểu hơn thôi
bây giờ, sau ki biểu diễn số đã cho theo cách này, chúng ta tạo ra các số nhỏ hơn số đã cho và đồng thời tính bằng dp nếu số đó thỏa mãn điều kiện đã cho. chúng ta bắt đầu tạo các só nguyên có số chữ số = 1 và sau đó đến số chữ số = n. các số nguyên có số chữ số ít hơn n có thể được phân tích bằng các đặt các chữ số ngoài cùng bên trái = 0

2) bài toán ví dụ
cho 2 số nguyên a và b, nhiệm vụ của mày là đưa tao tổng các chữ số nằm trong khoảng từ a đến b.
ví dụ: nếu a = 5, b = 11 thì đáp án là 5 + 6 + 7 + 8 + 9 + (1 + 0) + (1 + 1)
và ta vẫn có 1 <= a < b <= 10^18
- Bây giờ, chúng ta thấy rằng nếu chúng ta đã tính được đáp án cho trạng thái n-1 chữ số, thức là sn-1 sn-2...s2 s1 và chúng ta cần tính đáp án cho câu trả lời cho trạng thái có n chữ số sn sn-1 sn-2... s2 s1. vì vậy rõ ràng chúng ta có thể sử dụng kết quả của trạng thái trước đó thay vì phải tính tính lại lại lần nữa giúp giảm độ phức tạp. vì vậy cũng giống dp thường, cũng là theo tính chất chồng chéo các bài nhỏ lên nhau
hãy nghĩ ct truy hồi(trạng thái) cho dp này
trạng thái dp của chúng ta sẽ là dp(idx,tight,sum)
1) idx(index - i)
nó cho biết giá trị chỉ mục từ bên phải trong số nguyên đã cho(vị trí của số)
2) tight(chặt chẽ):
điều này sẽ cho biết phạm vi chữ số hiện tại có bị hạn chế bởi cái gì đó không, nếu chữ số hiện tại không bị giới hạn thì nó sẽ trải dài từ 0 -> 9. nếu không thì không trải dài
từ 0 -> idx
ví dụ: coi số nguyên giới hạn của chúng ta là 3245 và chúng ta cần tính F(3245):3 2 1 0(là idx)
chữ số: 3 2 4 5

phạm vi không giới hạn:
bây giờ giả sử số nguyên được tạo cho đến 3 1 _ _

chỉ số: 3 2 1 0
chữ số: 3 2 4 5
số nguyên tạo được: 3 1 _ _

ở đây chúng ta thấy chỉ số 2 có phạm vi không bị hạn chế. bây giờ mục 2 có thể có các chữ số từ 0 -> 9
Đối với phạm vi không bị giới hạn, tight = 0
Phạm vi bị hạn chế:
Bây giờ, giả sử số nguyên được tạo cho đến thời điểm hiện tại là:

3 2 _ _
chỉ số : 4 3 2 1  
chữ số : 3 2 4 5
số nguyên được tạo: 3 2 _ _

ở đây, chúng ta thấy chỉ số 2 có phạm vi hạn chế. Bây giờ chỉ mục 2 chỉ có thể có các chữ số từ phạm vi 0 đến 4 (bao gồm)
Đối với phạm vi giới hạn tight = 1
3) sum(tổng)
Tham số này sẽ lưu tổng các chữ số trong số nguyên được tạo từ msd đến idx.

Giá trị tối đa cho tổng tham số này có thể là 9*18 = 162, xem xét 18 chữ số trong số nguyên
Quan hệ trạng thái:
Ý tưởng cơ bản về quan hệ trạng thái rất đơn giản. Chúng tôi xây dựng dp theo kiểu từ trên xuống.
Giả sử chúng ta đang ở đầu tiên có chỉ mục idx. Vì vậy ban đầu tổng sẽ bằng 0.
Do đó, chúng ta sẽ điền chữ số ở chỉ mục bằng các chữ số trong phạm vi của nó. Giả sử phạm vi của nó là từ 0 đến k (k<=9, tùy thuộc vào giá trị tight) và tìm nạp câu trả lời từ trạng thái tiếp theo có chỉ số = idx-1 và sum = tổng trước đó + chữ số được chọn.

int ans = 0;
cho (int i=0; i<=k; i++) {
   ans += state(idx-1, newTight, sum+i)
trạng thái (idx, tight, sum) = ans;

Làm cách nào để tính giá trị newTight?
Giá trị tight mới của một trạng thái phụ thuộc vào trạng thái trước đó của nó. Nếu dạng giá trị tight ở trạng thái trước đó là 1 và chữ số tại idx được chọn là Digit[idx](tức là chữ số tại idx trong số nguyên giới hạn) thì chỉ có giá trị tight mới của chúng ta sẽ là 1 vì nó chỉ cho biết rằng số được hình thành cho đến bây giờ là tiền tố của số nguyên giới hạn.

// DigitTaken là chữ số được chọn
// digit[idx] là chữ số trong giới hạn
// số nguyên tại chỉ mục idx từ phải sang
// previoTight là dạng giá trị tight trước đó
// tình trạng

newTight = previousTight & (digitTake == digit[idx])
Dưới đây là cách thực hiện phương pháp trên
# CODE PYTHON:

dp = [[[-1 for i in range(2)] for j in range(180)]for k in range(20)]
def getDigits(x, digit):
    while x:
        digit.append(x % 10)
        x //= 10
def digitSum(index, sumof, tight, digit):
    if index == -1:
        return sumof
if dp[index][sumof][tight] != -1 and tight != 1:
    return dp[index][sumof][tight]
ret = 0
k = digit[index] if tight else 9
for i in range(0, k+1):
    newTight = tight if digit[index] == i else 0
    ret += digitSum(index-1, sumof+i, newTight, digit)
if not tight:
    dp[index][sumof][tight] = ret
return ret
def rangeDigitSum(a, b):
digitA = []
getDigits(a-1, digitA)

ans1 = digitSum(len(digitA)-1, 0, 1, digitA)
digitB = []
getDigits(b, digitB)

ans2 = digitSum(len(digitB)-1, 0, 1, digitB)
return ans2-ans1``
a, b = 123, 1024
print("digit sum for given range: ", rangeDigitSum(a, b))

# CODE C++:

#include "bits/stdc++.h"
using namespace std;
long long dp[20][180][2];
void getDigits(long long x, vector <int> &digit)
{
    while (x)
    {
        digit.push_back(x%10);
        x /= 10;
    }
}
long long digitSum(int idx, int sum, int tight,
                          vector <int> &digit)
{
    if (idx == -1)
       return sum;
    if (dp[idx][sum][tight] != -1 and tight != 1)
        return dp[idx][sum][tight];
 
    long long ret = 0;
    int k = (tight)? digit[idx] : 9;
 
    for (int i = 0; i <= k ; i++)
    {
        int newTight = (digit[idx] == i)? tight : 0;
        ret += digitSum(idx-1, sum+i, newTight, digit);
    }
 
    if (!tight)
      dp[idx][sum][tight] = ret;
 
    return ret;
}
int rangeDigitSum(int a, int b)
{
    memset(dp, -1, sizeof(dp));
    vector<int> digitA;
    getDigits(a-1, digitA);
    long long ans1 = digitSum(digitA.size()-1, 0, 1, digitA);
    vector<int> digitB;
    getDigits(b, digitB);
    long long ans2 = digitSum(digitB.size()-1, 0, 1, digitB);
 
    return (ans2 - ans1);
}
int main()
{
    long long a = 123, b = 1024;
    cout << "digit sum for given range : "
         << rangeDigitSum(a, b) << endl;
    return 0;
}

# **nguồn code: geeksforgeeks**

**output code:
tổng chữ số cho phạm vi đã cho: 12613**

Độ phức tạp về thời gian :
Có tổng số trạng thái idx * sum * tight và anh đang thực hiện 0 đến 9 lần lặp để truy cập mọi trạng thái. Do đó, Độ phức tạp về thời gian sẽ là O(10 * idx * sum * tight) . Ở đây, ta quan sát thấy rằng tight = 2 và idx có thể tối đa là 18 đối với số nguyên không dấu 64 bit và hơn nữa, tổng sẽ tối đa là 9 * 18 khoảng 200. Vì vậy, tổng thể chúng tôi có 10 * 18 * 200 * 2 khoảng 10^5 lần lặp có thể được thực hiện dễ dàng trong 0,01 giây .

Độ phức tạp của không gian:

Độ phức tạp về không gian của thuật toán này là O(idx * sum * tight) vì nó sử dụng mảng dp có kích thước d*sum*tight. trong đó idx là số chữ số trong số, tổng là tổng của các chữ số và tight là giá trị bool hoặc int cho biết chữ số hiện tại có bị giới hạn ở chữ số trong số hay không.

Vấn đề trên cũng có thể được giải quyết bằng cách sử dụng đệ quy đơn giản mà không cần đệ quy có

# Kết Thúc:
Trên là Sơ lược về dp digit cực kì cơ bản bằng phương pháp đệ quy. ta vẫn có thể chạy for hoặc dùng đệ quy có nhớ để giải quyết.