Đú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
Giả sử ta có
Ta thực hiện việc gán giá trị cho phần tử
Giả sử ta đã điền các chữ số ở trước
Trường hợp không giới hạn sẽ xảy ra nếu các số được điền trước
Ở đây, vì
Giả sử ta đã điền các chữ số ở trước
Trường hợp có giới hạn sẽ xảy ra nếu các số được điền trước
Ở đây, ta có
Từ
Trong đó:
Khi này, ta sẽ gọi hàm
Độ phức tạp của QHĐ chữ số thường sẽ có dạng:
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
Giới hạn:
Ví dụ:
Ta có các trạng thái QHĐ:
Tính giá trị:
Khi ta ở trạng thái
Nếu
Ta có thể điền các số từ
Chuyển trạng thái:
Giả sử ta đã điền được số cho
Nếu trạng thái của ta đang là
#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ố
Giới hạn:
Bài toán này tương tự với bài toán ở ví dụ
Nếu
Một điều nữa là hàm
#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
Giới hạn:
Gọi
Với
Ta thấy rằng các số
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
Tổng các số đếm được sẽ là đáp án của bài toán gốc.
Ta có
Nếu
Việc chuyển đổi trạng thái
#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à
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
Vì các giá trị của trạng thái QHĐ 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
Một số
Giới hạn:
Ta có
Nếu
Nếu trạng thái của ta đang là
Vì
#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
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
Việc tìm các số đặc biệt
Ta có
Nếu
Nếu trạng thái của ta đang là
#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
Giới hạn:
Ta có
Nếu
Nếu trạng thái của ta đang là
Đồng thời, nếu
#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ố