<h1>Quy hoạch động chữ số (Digit Dynamic Programming)</h1>
<p>Như tên gọi của nó, quy hoạch động chữ số là một kĩ thuật quy hoạch động trong đó chúng ta sử dụng các chữ số của các số để tìm ra kết quả.</p>
<h2>Những kiến thức cần biết</h2>
<p>Để hiểu rõ bài viết này, bạn cần có kiến thức về những nội dung sau:</p>
<ul>
<li>Đệ quy (Recursion)</li>
<li>Đệ quy có nhớ (Memoization)</li>
<li>Quy hoạch động (Dynamic Programming)</li>
</ul>
<h2>Quy hoạch động chữ số là gì?</h2>
<p>Hầu hết chúng ta đều đã đọc và nghe về quy hoạch động và cách nó sử dụng các bài toán con lặp lại và ghi nhớ để giải quyết một bài toán lớn hơn. Quy hoạch động chữ số là một kỹ thuật như vậy, nhưng ở đây, như tên gọi của nó, chúng ta sử dụng các chữ số của một số. Điều này có nghĩa là để có được kết quả cuối cùng, chúng ta sử dụng các chữ số của một số.</p>
<p>Quy hoạch động chữ số rất hữu ích trong việc giải các bài toán liên quan đến một phạm vi số, chẳng hạn như tìm tổng các chữ số của các số giữa hai số a và b hoặc tìm số lần một chữ số cụ thể xuất hiện trong các số trong phạm vi [a, b]. Đây là những bài toán mà quy hoạch động chữ số trở nên hữu ích. Và rõ ràng là qua các yêu cầu bài toán, những yêu cầu này có liên quan đến các chữ số của các số liên quan.</p>
<p>Chúng ta hãy cùng tìm hiểu thêm về cách quy hoạch động chữ số hoạt động và ý tưởng chính đằng sau nó.</p>
<p>Ý tưởng chính mà quy hoạch động chữ số có thể giải các câu hỏi như vậy là chúng ta coi các số là một chuỗi các chữ số và cố gắng xây dựng các số trong phạm vi cho trước theo từng chữ số khi chúng ta thực hiện và cũng tính toán kết quả theo từng chữ số.</p>
<p>Hãy lấy một ví dụ để hiểu rõ hơn về cách thức hoạt động của quy hoạch động chữ số.</p>
<h2>Bài toán</h2>
<p>Tìm tổng số lần chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi></math> xuất hiện trong các số trong phạm vi <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>, trong đó <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>&lt</mo><mi>b</mi></math>.</p>
<p>Ví dụ, trong trường hợp <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>=</mo><mi>5</mi></math>, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi><mo>=</mo><mi>10</mi></math>, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi><mo>=</mo><mi>1</mi></math>, câu trả lời sẽ là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>1</mi></math> vì chỉ có số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>10</mi></math> có chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>1</mi></math>.</p>
<p>Nhưng làm thế nào để chúng ta có thể giải quyết bài toán này bằng cách sử dụng quy hoạch động chữ số? Chúng ta có thể thực hiện bằng cách xây dựng một số theo từng chữ số sao cho nó nằm trong phạm vi đã cho và trong khi đếm số lần chúng ta đặt một chữ số là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>1</mi></math>. Nhưng chúng ta có thể làm điều này như thế nào? Hãy bắt đầu với một trường hợp cơ sở là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>=</mo><mi>0</mi></math>.</p>
<h3>Tìm kết quả cho phạm vi từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>b</mn></math></h3>
<p>Để tìm kết quả, chúng ta coi số của mình là một chuỗi chữ số. Chúng ta cần xây dựng các số theo từng chữ số cho đến khi chúng nằm trong phạm vi được cung cấp cho chúng ta trong đề bài. Vì <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>=</mo><mi>0</mi></math> nên ban đầu chuỗi rỗng và chúng ta có thể thêm các chữ số vào đó.</p>
<p>Chúng ta bắt đầu thêm các chữ số từ trái sang phải, tại mỗi thời điểm, chúng ta có một vị trí mà chúng ta có thể nhập một chữ số để tạo thành một số mới, sau đó lặp lại cho vị trí tiếp theo. Bây giờ, chúng ta cần xem xét các lựa chọn mà chúng ta có cho một vị trí cụ thể. Chúng ta không thể chỉ thêm bất kỳ chữ số nào từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>9</mi></math>, vì chúng ta cần đảm bảo rằng số kết quả thỏa mãn phạm vi từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>.</p>
<p>Hãy lấy một ví dụ để hiểu rõ hơn về điều này. Giả sử <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>=</mo><mi>0</mi></math> và <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi><mo>=</mo><mi>83625</mi></math>. Giả sử chuỗi số mà chúng ta đang xây dựng bằng cách thêm các chữ số cho đến bây giờ là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"8362_"</mi></math>. Trong lần đệ quy tiếp theo, chúng ta phải thêm một chữ số khác vào bên phải của <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>2</mi></math>, nhưng chúng ta có thể thêm bất kỳ chữ số nào từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>9</mi></math> không?</p>
<p>Khi ta thêm bất kỳ chữ số nào lớn hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>5</mi></math> sẽ khiến số lớn hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> và do đó số nằm ngoài phạm vi <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>. Điều này có nghĩa là đối với vị trí này, chúng ta chỉ có thể thêm các chữ số từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>5</mi></math>.</p>
<p>Mặt khác, nếu chuỗi chúng ta đã xây dựng cho đến bây giờ là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"734__"</mi></math>, chúng ta không có hạn chế nào đối với bất kỳ vị trí còn trống nào. Chúng ta có thể đặt bất kỳ chữ số nào từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>9</mi></math> vào các vị trí còn lại bên phải. Điều này là do chữ số đầu tiên <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>7</mi></math> tự nó đảm bảo rằng số đầy đủ sẽ luôn nhỏ hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> bất kể chữ số nào được nhập ở bên phải của nó.</p>
<p>Nhận xét này rất quan trọng để thực hiện quy hoạch động chữ số. Rõ ràng là chúng ta có một số vị trí mà chúng ta cần thêm các chữ số và xây dựng một số trong phạm vi đã cho. Số lượng vị trí sẽ phụ thuộc vào <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> và bằng với số chữ số của <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>.</p>
<p>Bây giờ, chúng ta có một số vị trí mà chúng ta cần thêm các chữ số. Chúng ta có thể bắt đầu từ vị trí ngoài cùng bên trái và tiếp tục thêm các chữ số. Đồng thời, chúng ta cũng sẽ cần một số thông tin về những chữ số nào có thể được thêm vào vị trí này tùy thuộc vào các chữ số trước đó như chúng ta đã thấy trong ví dụ trên. Vậy làm thế nào để biết điều này?</p>
<p>Một cách khả thi là theo dõi toàn bộ chuỗi được xây dựng cho đến hiện tại, sau đó kiểm tra bằng cách đặt tất cả các chữ số từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>9</mi></math> và chỉ tiếp tục với những chữ số nhỏ hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>, và bỏ qua những số còn lại. Nhưng có một cách tiếp cận đơn giản hơn.</p>
<p>Trong ví dụ, chúng ta có một hạn chế đối với các chữ số mà chúng ta chỉ có thể thêm khi chuỗi được xây dựng cho đến hiện tại giống với số đó. Nếu chúng ta đã thêm một chữ số nhỏ hơn chữ số ở vị trí tương ứng của <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> vào chuỗi thì chúng ta không có hạn chế nào cho các chữ số phía sau.</p>
<p>Nếu chuỗi được xây dựng cho đến hiện tại là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"83___"</mi></math>, chúng ta không thể đặt bất kỳ chữ số nào lớn hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>6</mi></math> ở vị trí tiếp theo, nhưng nếu chuỗi của chúng ta là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"82___"</mi></math>, chúng ta không có hạn chế nào, vì chữ số 2 ở vị trí thứ hai đảm bảo rằng số của chúng ta sẽ luôn nhỏ hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>.</p>
<p>Điều này sẽ trở nên dễ dàng bằng cách sử dụng một biến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>bool</mi></math> làm tham số cho hàm đệ quy. Nếu biến này được gán thành <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>true</mi></math>, điều đó có nghĩa là chúng ta có một hạn chế và chúng ta có thể thêm các chữ số từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến chữ số ở vị trí tương ứng trong <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>
vào chuỗi, nếu không thì số kết quả sẽ nằm ngoài phạm vi. Và nếu biến này được gán thành <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>false</mi></math>, chúng ta không có hạn chế nào. Bất cứ khi nào chúng ta thêm một chữ số vào chuỗi bằng với chữ số tương ứng trong <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>, chúng ta phải gán biến này thành <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>true</mi></math>. Và nếu chúng ta thêm một chữ số nhỏ hơn chữ số tương ứng trong <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>, chúng ta đặt biến này thành <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>false</mi></math> và vẫn là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>false</mi></math> cho các vị trí tiếp theo.</p>
<p>Đến bây giờ, bài toán ban đầu có thể được giải quyết rất dễ dàng vì bất cứ khi nào chúng ta thêm chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi></math> vào chuỗi mà chúng ta đang xây dựng, chúng ta có thể cộng thêm <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>1</mi></math> vào kết quả, cuối cùng chúng ta sẽ có tổng số lần chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi></math> xuất hiện trong phạm vi từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>.</p>
<h3>Tìm kết quả cho phạm vi từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>a</mn></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>b</mn></math></h3>
<p>Chúng ta đã biết giải pháp cho phạm vi <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> và chúng ta cũng có thể tính toán giải pháp cho phạm vi <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> bằng cùng một phương pháp.</p>
<p>Giải pháp cho phạm vi từ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> sẽ đơn giản là:</p>
<pre><code class="language-cpp">calc(a, b) = calc(0, b) - calc(0, a - 1);</code></pre>
<p>Tại sao điều này lại đúng? Bởi vì khi trừ <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>calc(0, a - 1)</mi></math> khỏi <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>calc(0, b)</mi></math> chúng ta đảm bảo rằng tất cả các số nhỏ hơn <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> đều bị loại trừ, do đó cung cấp cho chúng ta giải pháp cho phạm vi <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> đến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>.</p>
<h3>Các trạng thái quy hoạch động và code mẫu</h3>
<p>Cho đến bây giờ, chúng ta chỉ xem xét cách chúng ta có thể giải quyết một bài toán bằng cách sử dụng quy hoạch động chữ số, bây giờ chúng ta hãy thảo luận chi tiết về giải pháp.</p>
<p>Chúng ta biết rằng mọi giải pháp quy hoạch động đều có các trạng thái, chỉ những tham số cần thiết để xác định từng trạng thái trong bài toán. Trong trường hợp này, chúng ta có ba trạng thái. Một trạng thái là tham số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>pos</mi></math> chỉ vị trí mà một chữ số mới sẽ được chèn vào và nó nhận giá trị tối đa là số lượng chữ số của <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>. Trạng thái thứ hai là tham số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>flag</mi></math> mà chúng ta đã định nghĩa trước đó, biểu thị liệu chúng ta có giới hạn về các chữ số có thể được chọn cho vị trí hiện tại hay không. Trạng thái thứ ba sẽ là tham số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>cnt</mi></math> biểu thị số chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi></math> mà chúng ta đã đưa vào cho đến hiện tại.</p>
<p>Do đó, mảng quy hoạch động của chúng ta sẽ trông như này <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f[pos][flag][cnt]</mi></math>.</p>
<h4>Code mẫu bằng C++</h4>

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

int f[18][19][2];

// Hàm calc() dùng để đếm số chữ số d xuất hiện trong các số từ 0 đến k
// Trong đó, k được biểu diễn dưới dạng vector digits
int calc(vector<int> & digits, int d, int pos, int cnt, bool flag){
    // Trường hợp đã duyệt hết qua các vị trí
    if (pos >= digits.size()) return cnt;

    // Trạng thái này đã được tính toán trước đó
    if (f[pos][cnt][flag] != -1) return f[pos][cnt][flag];
    
    // limit biểu thị cho giới hạn cho chữ số được thêm vào ở vị trí pos
    int limit = 9;

    // Trong trường hợp flag là true, chữ số được thêm vào sẽ phải nhỏ hơn hoặc bằng chữ số ở vị trí tương ứng trên k
    if (flag == 1) limit = digits[pos];
    
    // res là kết quả tính toán của trạng thái hiện tại
    int res = 0;
    
    // Chúng ta duyệt qua tất cả các chữ số có thể được thêm vào vị trí này
    for (int i = 0; i <= limit; i++){
        // Trong lần gọi hàm tiếp theo, chúng ta cần xác định giá trị mới của flag
        bool newFlag = flag;
        
        // Nếu flag là 1 và chữ số đang chọn bằng với chữ số ở vị trí tương ứng trên k thì giá trị mới của flag là true
        if (flag == 1 && i == digits[pos]) newFlag = true;
        // Nếu không, chúng ta không có hạn chế trong lần gọi hàm tiếp theo
        else newFlag = false;
        
        // Giá trị mới của cnt cho lần gọi hàm tiếp theo
        int newCnt = cnt;
        
        // Chữ số được thêm vào là d thì cnt sẽ được tăng lên 1 ở lần gọi hàm tiếp theo
        if (i == d) newCnt++;
        
        // Tiếp tục đệ quy và cập nhật kết quả
        res += calc(digits, d, pos + 1, newCnt, newFlag);
        
    }
    
    // Trả về kết quả của trạng thái hiện tại
    return f[pos][cnt][flag] = res;
}

int main() {
    long long a, b;
    int d;
    cin >> a >> b >> d;
    
    // vector để lưu trữ các chữ số trong a - 1 và b
    vector<int> aDigits, bDigits;
    
    // lấy các chữ số từ a - 1 và b
    a--;
    while (a > 0){
        aDigits.push_back(a % 10);
        a /= 10;
    }
    reverse(aDigits.begin(), aDigits.end());
    while (b > 0){
        bDigits.push_back(b % 10);
        b /= 10;
    }
    reverse(bDigits.begin(), bDigits.end());
    
    // Khởi tạo mảng quy hoạch động
    memset(f, -1, sizeof(f));
    
    // Tính toán kết quả trong đoạn 0 đến a - 1
    int resA = calc(aDigits, d, 0, 0, true);
    
    // Khởi tạo lại mảng quy hoạch động
    memset(f, -1, sizeof(f));
    
    // Tính toán kết quả trong đoạn 0 đến b
    int resB = calc(bDigits, d, 0, 0, true);
    
    // Kết quả trong đoạn a đến b
    int res = resB - resA;
    
    cout << res;
    
    return 0;
}

<h4>Sample input</h4>
<pre><code class="language-cpp">10 20 2</code></pre>
<h4>Sample output</h4>
<pre><code class="language-cpp">2</code></pre>
<h3>Trường hợp đặc biệt: <math xmlns="http://www.w3.org/1998/Math/MathML"><mn>d = 0</mn></math></h3>
<p>Nếu bạn chạy đoạn code trên với <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>d</mi><mo>=</mo><mi>0</mi></math>, nó sẽ trả về một kết quả sai. Điều này là do theo thuật toán của chúng ta, bất cứ khi nào thêm <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> vào chuỗi xây dựng, chúng ta sẽ tăng số đếm <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>cnt</mi></math>. Nhưng điều này có nghĩa là khi chúng ta xây dựng chuỗi, chúng ta sẽ thêm các chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> vô nghĩa, ví dụ như <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"01"</mi></math>, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"02"</mi></math>, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>"03"</mi></math>, ... và những chữ số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> vô nghĩa đó được đếm dẫn đến sai kết quả.</p>
<p>Để giải quyết điều này, chúng ta sử dụng thêm một biến <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>bool</mi></math> là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>isEmpty</mi></math>. Nếu <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>isEmpty</mi></math> là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>true</mi></math> thì có nghĩa là chuỗi được xây dựng cho đến hiện tại đang là số <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> và nếu chúng ta thêm <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> vào chuỗi thì chúng ta không tính nó là một chữ số vì nó không có giá trị và nếu <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>isEmpty</mi></math> là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>false</mi></math> thì có nghĩa là chuỗi của chúng ta khác <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> và chúng ta phải đếm <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>0</mi></math> là một chữ số.</p>
<h4>Code mẫu bằng C++</h4>

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

int f[18][19][2][2];

// Hàm calc() dùng để đếm số chữ số d xuất hiện trong các số từ 0 đến k
// Trong đó, k được biểu diễn dưới dạng vector digits
int calc(vector<int> & digits, int d, int pos, int cnt, bool flag, bool isEmpty){
    // Trường hợp đã duyệt hết qua các vị trí
    if (pos >= digits.size()) return cnt;

    // Trạng thái này đã được tính toán trước đó
    if (f[pos][cnt][flag][isEmpty] != -1) return f[pos][cnt][flag][isEmpty];
    
    // limit biểu thị cho giới hạn cho chữ số được thêm vào ở vị trí pos
    int limit = 9;

    // Trong trường hợp flag là true, chữ số được thêm vào sẽ phải nhỏ hơn hoặc bằng chữ số ở vị trí tương ứng trên k
    if (flag == 1) limit = digits[pos];
    
    // res là kết quả tính toán của trạng thái hiện tại
    int res = 0;
    
    // Chúng ta duyệt qua tất cả các chữ số có thể được thêm vào vị trí này
    for (int i = 0; i <= limit; i++){
        // Trong lần gọi hàm tiếp theo, chúng ta cần xác định giá trị mới của flag
        bool newFlag = flag;

		// Giá trị mới của isEmpty cho lần gọi hàm tiếp theo
		bool newIsEmpty = false;

		// Nếu chữ số đang chọn là 0 và chuỗi vẫn đang là 0 thì vẫn sẽ tiếp tục là 0
		if (i == 0 && isEmpty == true) newIsEmpty = true;
        
        // Nếu flag là 1 và chữ số đang chọn bằng với chữ số ở vị trí tương ứng trên k thì giá trị mới của flag là true
        if (flag == 1 && i == digits[pos]) newFlag = true;
        // Nếu không, chúng ta không có hạn chế trong lần gọi hàm tiếp theo
        else newFlag = false;
        
        // Giá trị mới của cnt cho lần gọi hàm tiếp theo
        int newCnt = cnt;
        
        // Cập nhật biến đếm
        if (i == d && (d != 0 || isEmpty == false)) newCnt++;
        
		// Nếu chữ số đang chọn khác 0 thì chuỗi sẽ không còn là 0
		if (i != 0) newIsEmpty = false;

        // Tiếp tục đệ quy và cập nhật kết quả
        res += calc(digits, d, pos + 1, newCnt, newFlag, newIsEmpty);   
    }
    
    // Trả về kết quả của trạng thái hiện tại
    return f[pos][cnt][flag][isEmpty] = res;
}

int main() {
    long long a, b;
    int d;
    cin >> a >> b >> d;
    
    // vector để lưu trữ các chữ số trong a - 1 và b
    vector<int> aDigits, bDigits;
    
    // lấy các chữ số từ a - 1 và b
    a--;
    while (a > 0){
        aDigits.push_back(a % 10);
        a /= 10;
    }
    reverse(aDigits.begin(), aDigits.end());
    while (b > 0){
        bDigits.push_back(b % 10);
        b /= 10;
    }
    reverse(bDigits.begin(), bDigits.end());
    
    // Khởi tạo mảng quy hoạch động
    memset(f, -1, sizeof(f));
    
    // Tính toán kết quả trong đoạn 0 đến a - 1
    int resA = calc(aDigits, d, 0, 0, true, true);
    
    // Khởi tạo lại mảng quy hoạch động
    memset(f, -1, sizeof(f));
    
    // Tính toán kết quả trong đoạn 0 đến b
    int resB = calc(bDigits, d, 0, 0, true, true);
    
    // Kết quả trong đoạn a đến b
    int res = resB - resA;
    
    cout << res;
    
    return 0;
}

<h4>Sample input</h4>
<pre><code class="language-cpp">100 110 0</code></pre>
<h4>Sample output</h4>
<pre><code class="language-cpp">12</code></pre>

### Độ phức tạp
Thuật toán có độ phức tạp là $O(L \times C \times 10)$, với:
- $L$ là số chữ số của $b$ (ở đây tối đa là $18$).
- $C$ là số lượng trạng thái của biến đếm $cnt$ (ở đây tối đa là $19$).
- $10$ là số chữ số có thể được duyệt tại mỗi vị trí.

Đến đây, bài toán ban đầu của chúng ta đã được giải quyết một cách hoàn chỉnh. Các bạn có thể làm bài tương tự: <a href="https://lqdoj.edu.vn/problem/justadigitproblem">Một bài tập thú vị về chữ số - LQDOJ</a>.

## Bài tập áp dụng
- <a href="https://lqdoj.edu.vn/problem/justadigitproblem">Một bài tập thú vị về chữ số - LQDOJ</a>
- <a href="https://oj.vnoi.info/problem/atcoder_dp_s">Digit Sum - VNOJ</a>