Đúng như tên gọi của nó, Quy hoạch động chữ số hay Digit DP là một kĩ thuật QHĐ nhằm giải quyết các bài toán liên quan đến chữ số.
Các bài QHĐ chữ số sẽ có mô tả như sau: Cho một đoạn số , hãy đếm số lượng số nguyên trong đoạn thỏa mãn yêu cầu đề bài.
Gọi là số lượng số nguyên nằm trong đoạn thỏa mãn yêu cầu đề bài. Khi này ta có thể tính được đáp án của bài toán bằng công thức: hoặc với là một hàm trả về nếu thỏa mãn yêu cầu và nếu không thỏa mãn.
Để xây dựng hàm , ta sẽ xem các số trong đoạn như một xâu kí tự: Ta có với là số chữ số trong . Ta sẽ tạo các số nhỏ hơn hoặc bằng , và thực hiện việc gán giá trị cho các chữ số của theo chiều từ trái sang phải.
Giả sử ta có :
Ta thực hiện việc gán giá trị cho phần tử theo hai trường hợp: trường hợp có và không có giới hạn.
Giả sử ta đã điền các chữ số ở trước bằng các giá trị sau:
Trường hợp không giới hạn sẽ xảy ra nếu các số được điền trước có thứ tự từ điển nhỏ hơn hẳn , hay . Khi này, ta có thể điền các chữ số từ đến .
Ở đây, vì nên rơi vào trường hợp không giới hạn. Ta có thể kết luận như vậy vì dù có gán bằng chữ số nào đi nữa thì các số có dạng cũng sẽ nhỏ hơn . Vì vậy ta có thể gán cho các chữ số từ đến .
Giả sử ta đã điền các chữ số ở trước bằng các giá trị sau:
Trường hợp có giới hạn sẽ xảy ra nếu các số được điền trước là một tiền tố của số . Khi này, ta chỉ có thể điền các chữ số từ đến .
Ở đây, ta có là một tiền tố của nên rơi vào trường hợp có giới hạn. Giả sử ta gán . Khi này, các số có dạng sẽ lớn hơn , và các số có dạng này là các số mà ta không cần xét đến. Vì lí do trên nên ta chỉ có thể gán cho các chữ số từ đến .
Từ trường hợp trên, ta có các trạng thái QHĐ cần thiết để giải một bài toán QHĐ chữ số:
Trong đó:
Khi này, ta sẽ gọi hàm để tính :
Độ phức tạp của QHĐ chữ số thường sẽ có dạng: , trong đó:
Ta cùng xem qua một số bài toán ví dụ để hiểu rõ hơn.
Tóm tắt: Cho hai số nguyên không âm và , tính tổng chữ số của các số trong đoạn .
Giới hạn: .
Ví dụ: .
Ta có các trạng thái QHĐ: với , có định nghĩa như trên và là tổng của các chữ số đã điền.
Tính giá trị:
Khi ta ở trạng thái :
Nếu , ta không còn vị trí nào để điền giá trị, ta trả về giá trị . Nếu lớn hơn , ta sẽ thực hiện gán giá trị cho .
Ta có thể điền các số từ đến cho số , với nếu , hoặc nếu .
Chuyển trạng thái:
Giả sử ta đã điền được số cho , ta sẽ bắt đầu điền số tiếp theo.
Nếu trạng thái của ta đang là , và ta điền , ta sẽ chuyển trạng thái tiếp theo :
#include <bits/stdc++.h>
using namespace std;
long long dp[2][20][200];
int x[20];
long long f(int idx, bool smaller, int sum);
long long G(long long X);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long a, b; cin >> a >> b;
cout << G(b) - G(a - 1);
return 0;
}
long long f(int idx, bool smaller, int sum){
if(idx < 0) return sum;
long long &memo = dp[smaller][idx][sum];
if(memo != -1) return memo;
// tìm limit
int lim = smaller ? 9 : x[idx];
memo = 0;
// điền chữ số
for(int digit = 0; digit <= lim; ++digit){
// chuyển trạng thái
memo += f(idx - 1, smaller || (digit < lim), sum + digit);
}
return memo;
}
long long G(long long X){
// phân tích X thành các chữ số
int n = 0; x[n] = 0;
while(X > 0){
x[n++] = X % 10;
X /= 10;
}
memset(dp, -1, sizeof(dp));
// chưa điền số nào => sum = 0
return f(n - 1, 0, 0);
}
Độ phức tạp của thuật toán này là .
Ngoài cách giải QHĐ chữ số, ta cũng có thể giải bằng phương pháp khác.
Tóm tắt: Cho hai số và , đếm số lượng số từ đến có tổng chữ số chia hết cho , modulo .
Giới hạn: , .
Bài toán này tương tự với bài toán ở ví dụ , có trạng thái QHĐ nhưng có một chút khác biệt.
Nếu , hàm của ta trả về nếu và trong các trường hợp còn lại. Đồng thời, việc chuyển trạng thái sang cũng thay đổi thành .
Một điều nữa là hàm cũng sẽ xét cả số mặc dù bài toán không yêu cầu nên kết quả bài toán sẽ là: .
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int MOD = 1e9 + 7;
long long dp[2][110][N];
int x[N];
int D;
string K;
long long f(int idx, bool smaller, int sum);
long long G(string &X);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> K >> D;
cout << G(K);
return 0;
}
long long f(int idx, bool smaller, int sum){
if(idx < 0) return sum == 0;
long long &memo = dp[smaller][sum][idx];
if(memo != -1) return memo;
memo = 0;
int lim = smaller ? 9 : x[idx];
for(int i = 0; i <= lim; ++i){
memo += f(idx - 1, smaller || (i < lim), (sum + i) % D);
memo %= MOD;
}
return memo;
}
long long G(string &X){
int n = 0; x[n] = 0;
for(int i = X.length() - 1; i >= 0; --i){
x[n++] = X[i] - '0';
}
memset(dp, -1, sizeof dp);
return (f(n - 1, 0, 0) -1 + MOD) % MOD;
}
Độ phức tạp của thuật toán này là .
Tóm tắt: Cho cặp số , đếm số lượng số có tích với tổng chữ số của nó đó nằm trong đoạn .
Giới hạn: , .
Gọi là một số thỏa mãn điều kiện. Vì thỏa mãn điều kiện nên:
Với là tổng các chữ số của .
Ta thấy rằng các số , , là các số rất lớn, nhưng lại nhỏ một cách bất ngờ - .
Từ đây, ta có thể viết lại công thức trên như sau:
Qua công thức này, ta đã chuyển đổi bài toán sang một dạng khác đơn giản hơn: Cho chạy từ đến , đếm số lượng số từ đến có tổng chữ số bằng .
Tổng các số đếm được sẽ là đáp án của bài toán gốc.
Ta có trạng thái QHĐ: .
Nếu , hàm sẽ trả về nếu và trả về trong các trường hợp còn lại.
Việc chuyển đổi trạng thái , sang sẽ tương tự ví dụ .
#include <bits/stdc++.h>
using namespace std;
long long dp[2][20][180];
int x[20];
long long l, r;
long long s;
long long f(int idx, bool smaller, int sum);
long long G(long long X);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while(t--){
cin >> l >> r;
--l;
long long sum = 0;
for(s = 1; s <= 171; ++s){
sum += G(r / s) - G(l / s);
}
cout << sum << '\n';
}
return 0;
}
long long f(int idx, bool smaller, int sum){
if(idx < 0) return sum == s;
long long &memo = dp[smaller][idx][sum];
if(memo != -1) return memo;
int lim = smaller ? 9 : x[idx];
memo = 0;
for(int digit = 0; digit <= lim; ++digit){
memo += f(idx - 1, smaller || (digit < lim), sum + digit);
}
return memo;
}
long long G(long long X){
if(X <= 0) return 0;
int n = 0; x[n] = 0;
for(; X > 0; ++n){
x[n] = X % 10;
X /= 10;
}
memset(dp, -1, sizeof(dp));
return f(n - 1, 0, 0);
}
Độ phức tạp của thuật toán này là , với là giới hạn của tổng các chữ số đã được nhắc đến ở trên.
Nhiều bài toán QHĐ chữ số (giống như bài này) có thể yêu cầu ta tính đi tính lại các đoạn số với cùng một tính chất. việc này vô tình làm cho thuật toán của ta chạy chậm đi khi phải tính đi tính lại các số.
Một cách tối ưu cực kì hay ho chính là ta sẽ chỉ thực hiện việc memset một lần ở ngoài hàm , đồng thời bỏ trạng thái khi lưu kết quả của trạng thái.
Vì các giá trị của trạng thái QHĐ có phụ thuộc vào một giá trị cụ thể, nên không thể sử dụng lại cho các số tiếp theo. Bằng cách loại bỏ trạng thái khi lưu kết quả của trạng thái và xét riêng từng trường hợp , ta có thể sử dụng lại các kết quả đã được tính ở những lần trước.
Có thể xem qua đoạn code của bài toán khi áp dụng cách cài đặt mới:
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int x[N];
long long dp[N][172];
long long f(int idx, bool smaller, int sum);
long long G(long long X, long long sum);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof(dp));
int t; cin >> t;
while(t--){
long long x, y; cin >> x >> y;
--x;
long long cnt = 0;
for(int i = 1; i < 172; ++i){
cnt += G(y / i, i) - G(x / i, i);
}
cout << cnt << '\n';
}
return 0;
}
long long f(int idx, bool smaller, int sum){
if(sum < 0) return 0;
if(idx < 0) return !sum;
long long &memo = dp[idx][sum];
if(smaller && memo != -1) return memo;
int lim = smaller ? 9 : x[idx];
long long ans = 0;
for(int i = 0; i <= lim; ++i){
ans += f(idx - 1, smaller || (i < lim), sum - i);
}
if(smaller) return memo = ans;
return ans;
}
long long G(long long X, long long sum){
int n = 0;
while(X){
x[n++] = X % 10;
X /= 10;
}
return f(n - 1, 0, sum);
}
Độ phức tạp của thuật toán giờ đây giảm xuống còn: .
Tóm tắt: Cho cặp số và , với mỗi cặp số, đếm số lượng số nằm trong đoạn , modulo .
Một số là số khi số lượng chữ số bằng số lượng chữ số và bằng số lượng chữ số và có ít nhất một chữ số .
Giới hạn: , .
Ta có trạng thái QHĐ: với , có định nghĩa như các ví dụ trước và , , là số lượng số , , và .
Nếu , hàm trả về nếu , và trong các trường hợp còn lại.
Nếu trạng thái của ta đang là , và ta điền , ta sẽ chuyển trạng thái tiếp theo :
Vì là những số rất lớn, ta áp dụng cách tính thứ hai được nói ở phần lý thuyết: .
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long dp[51][51][51][51];
int x[51];
long long f(int idx, bool smaller, int three, int six, int nine);
long long G(string &X);
bool g(string &X);
int main (int argc, char const *argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof(dp));
int t; cin >> t;
while(t--){
string a, b; cin >> a >> b;
cout << (G(b) - G(a) + g(a) + MOD) % MOD << '\n';
}
return 0;
}
long long f(int idx, bool smaller, int three, int six, int nine){
if(idx < 0) return three > 0 && three == six && three == nine;
long long &memo = dp[idx][three][six][nine];
if(smaller && memo != -1) return memo;
long long ans = 0;
int lim = smaller ? 9 : x[idx];
for(int i = 0; i <= lim; ++i){
ans += f(idx - 1, smaller || (i < lim), three + (i == 3), six + (i == 6), nine + (i == 9));
ans %= MOD;
}
if(smaller) memo = ans;
return ans;
}
long long G(string &X){
int n = 0; x[n] = 0;
for(int i = X.length() - 1; i >= 0; --i){
x[n++] = X[i] - '0';
}
return f(n - 1, 0, 0, 0, 0);
}
bool g(string &X){
int three = 0, six = 0, nine = 0;
for(char c : X){
three += c == '3';
six += c == '6';
nine += c == '9';
}
return three > 0 && three == six && three == nine;
}
Độ phức tạp của thuật toán là: .
Tóm tắt: Ta có hàm trả về tổng bình phương các chữ số trong . Một số được gọi là số đặc biệt nếu dẫu áp dụng bao nhiêu lần cập nhật bằng công thức: . Cho cặp số , hãy cho biết số lượng số đặc biệt trong đoạn .
Giới hạn: , .
Một điều dễ nhận thấy đối với bài toán này là với mỗi , . Vì vậy, ta có thể viết lại bài toán như sau: hãy cho biết số lượng số trong đoạn mà là số đặc biệt.
Việc tìm các số đặc biệt có thể được thực hiện một cách đơn giản.
Ta có trạng thái QHĐ: với , có định nghĩa như các ví dụ trước và là tổng bình phương các chữ số đã được điền.
Nếu , hàm trả về nếu là một số đặc biệt và nếu không là số đặc biệt.
Nếu trạng thái của ta đang là , và ta điền , ta sẽ chuyển trạng thái tiếp theo :
#include <bits/stdc++.h>
using namespace std;
const int N = 1459;
long long dp[20][N];
int x[20];
vector<int> adj[N];
bitset<N> special;
void dfs(int u);
long long f(int idx, int smaller, int sum);
long long G(long long X);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof(dp));
for(int i = 1; i < N; ++i){
// xây dựng đồ thị với các cung: f(x) -> x
int x = i;
long long sum = 0;
while(x > 0){
int digit = x % 10;
x /= 10;
sum += digit * digit;
}
adj[sum].push_back(i);
}
// tìm các số đặc biệt <= 1458
dfs(1);
int t; cin >> t;
while(t--){
long long l, r; cin >> l >> r;
cout << G(r) - G(l - 1) << '\n';
}
return 0;
}
void dfs(int u){
if(special[u]) return;
special[u] = 1;
for(int v : adj[u]) dfs(v);
}
long long f(int idx, int smaller, int sum){
if(idx < 0) return !special[sum];
long long &memo = dp[idx][sum];
if(smaller && memo != -1) return memo;
int lim = smaller ? 9 : x[idx];
long long ans = 0;
for(int i = 0; i <= lim; ++i){
ans += f(idx - 1, smaller || (i < lim), sum + i * i);
}
if(smaller) return memo = ans;
return ans;
}
long long G(long long X){
int n = 0; x[n] = 0;
for(; X > 0; ++n){
x[n] = X % 10;
X /= 10;
}
return f(n - 1, 0, 0);
}
Độ phức tạp của thuật toán này là: .
Tóm tắt: Cho một hoặc nhiều cặp số nguyên không âm và , đếm số lượng các số trong đoạn mà trong dạng biểu diễn không có số .
Giới hạn: .
Ta có trạng thái QHĐ: với , có định nghĩa như các ví dụ trước và với nếu số được điền ở vị trí bằng và trong trường hợp còn lại.
Nếu , hàm trả về .
Nếu trạng thái của ta đang là , và ta điền , ta sẽ chuyển trạng thái tiếp theo :
Đồng thời, nếu thì ta không được điền .
#include <bits/stdc++.h>
using namespace std;
long long dp[2][20];
int x[20];
long long f(int idx, bool one, bool smaller);
long long G(long long X);
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof(dp));
long long a, b;
while(cin >> a >> b){
cout << G(b) - G(a - 1) << '\n';
}
return 0;
}
long long f(int idx, bool one, bool smaller){
if(idx < 0) return 1;
long long &memo = dp[one][idx];
if(smaller && memo != -1) return memo;
int lim = smaller ? 9 : x[idx];
long long sum = 0;
for(int digit = 0; digit <= lim; ++digit){
if(digit == 3 && one == 1) continue;
sum += f(idx - 1, digit == 1, smaller || (digit < lim));
}
if(smaller) memo = sum;
return sum;
}
long long G(long long X){
if(X < 0) return 0;
int n = 0; x[n] = 0;
for(; X > 0; ++n){
x[n] = X % 10;
X /= 10;
}
return f(n - 1, 0, 0);
}
Độ phức tạp của thuật toán này là .
Ngoài các trạng thái biểu thị đoạn số quen thuộc như , ta còn có một số trạng thái phổ biến khác như: