Random writing has been pushed to the front page… Thank you, Nuggets. We’ll work on it in a few days.
Digital DP problem solves the number of digits that meet the requirements in an interval. The digital DP in the force button basically belongs to medium or hard, and this kind of question often appears in coding interview. There are many digital DP templates on the web, but writing with a lot of state variables can be very stressful for beginners. Our chickens used to get their heads up when they heard the digit DP. Today, I chose an introductory template to understand the general method of digital DP, hard just digital DP, no longer afraid of digital DP!
Counting problem
Given two integers A and b, find the number of occurrences of all digits between a and b.
vector<int> countBetween(int a,int b)
{}Copy the codeTopic link www.acwing.com/problem/con…
Train of thought
Step 1 turns interval counting into a single point problem
Similar to the idea of prefix sums, since counting is definitely monotonic, assuming we already know the answer to the number I in 0 minus x, then
return count(b) - count(a - 1);
Copy the codeThe advantage of this method is that it can avoid the tedious of special processing of the starting point and end point, and can avoid repeated solution.
Step 2 n digit problem
All algorithms aside, if you were to do this problem with a pen, the natural thing to think about is sorting numbers by the number of bits. So let’s start with a simple problem, the number of occurrences between the numbers 0 and 9, CNT [n][I], of all the n digits.
We know that for all the units digits (n = 1:0,1,2,3,4,5,6,7,8,9), each digit occurs once, i.e
cnt[1][i] = 1
So n = 2,3,4… ? We naturally want to extend from low to high by transforming the big n-bit problem into its subproblem n-1, which is why counting problems on digits are suitable for dynamic programming state transitions.
So how do you go from low n minus 1 to high N? We might immediately think that since the answer in the n-1 bit CNT [n-1][I] is known, the answer in the n-1 bit is essentially adding the highest digit, and there are 10 possible digits in the highest digit (not counting the leading 0), so for an n-digit, CNT [n][I] = 10 * CNT [n-1][I]
When the highest digit is equal to “I”, any number that follows will increase the number of “I”. There are 10n−110^{n-1}10n−1, and this extra part will be added.
So, the highest position is also the state we want to consider. So we add a one-dimensional state to record the highest bit.
We define the state dp[n][v][I] as the number of occurrences of number I when the highest bit of n digit is V. State transitions are as follows
int f[N][N][N] = {}; // the number of times the number I occurs (statistic j)
void dp(a)
{
for(int n = 1; n < N; n++) // enumerate all digits n
for(int v = 0; v < N; v++) // enumerate the highest bit v
{
if(n == 1)
f[n][v][v] = 1;// If there is only one digit, each digit appears once
else
for(int j = 0; j < N; j++) // Statistics j
{
for(int k = 0; k < N; k++) // The number of occurrences of j contributes to the number of occurrences of n digits in all last n-1 digits starting with any k (regardless of the current highest digit)
f[n][v][j] += f[n- 1][k][j];
if(j == i)// In particular, if the current highest digit is the statistic j, then whatever the following digit is contributes an additional occurrence (the current highest digit).
f[n][v][j] += pow(10,n- 1); }}}Copy the codeStep 3 uses n-digit problems to solve arbitrary upper bound problems
We just analyzed the problem on n digits, which is actually 0.. To 999.. This interval is analyzed, and since the original problem is a specific number as the upper limit, is not free to take from 0 to 999… How do we borrow the answer to the n digit problem?
For all 0-n-1 digits, the answer is unaffected by this upper bound and can therefore be obtained directly as described above.
for(int i = 1; i < n; i++)
for(intj = i ! =1; j < N; j++)
ans += f[i][j][c];
Copy the codeAnd for n digits, we have to be careful not to go beyond this upper bound.
The idea used here is that we divide each problem into two scenarios: one is to take the upper limit ana_nan and the other is to take some number between 0 ~ an−10 \sim a_{n} -10 ~ an−1. Why do you do that? Suppose x=xn−1xn−2… X0 ‾ x = \ overline {x_ x_ {n – 1} {2} n -… X_0} x = xn xn – 1-2… X0, in fact, if we select 0 ~ an−10 \sim A_n-10 ~ an−1 when the upper limit of one digit is not reached ana_{n}an, then the remaining digits can be freely ranged from 0 to 999.. That is, you can use the n-1 digit answer.
So the statistical answer breaks down into two parts
The first part does not consider the contribution of the target number in the prefix to the answer.
for(int hv = 0; hv < v; hv ++)
ans += dp[i+1][hv][c];
Copy the codeThe second part is the additional contribution to the answer that the prefix contains the target number C.
If xix_ixi is the highest digit, last is the number of the target digit c in the prefix, and the current digit is 0 ~ xi−10 \sim X_I-10 ~ xi−1, then the number of answers can be calculated according to the multiplication principle: 10^{I}10i = 10^{I}10i = 10^{I}10i = 10^{I}
ans += last * v * pow(10,i);
Copy the codeAt this point, we have completed all the difficult points in this problem.
code
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 10;
int f[N][N][N] = {}; // the number of times the number I occurs (statistic j)
void dp(a)
{
for(int n = 1; n < N; n++) // enumerate all digits n
for(int v = 0; v < N; v++) // enumerate the highest bit v
{
if(n == 1)
f[n][v][v] = 1;// If there is only one digit, each digit appears once
else
for(int j = 0; j < N; j++) // Statistics j
{
for(int k = 0; k < N; k++) // The number of occurrences of j contributes to the number of occurrences of n digits in all last n-1 digits starting with any k (regardless of the current highest digit)
f[n][v][j] += f[n- 1][k][j];
if(j == v)// In particular, if the current highest digit is the statistic j, then whatever the following digit is contributes an additional occurrence (the current highest digit).
f[n][v][j] += pow(10,n- 1); }}}int count(int a,int c) // The upper limit is a, the number of occurrences of the number c
{
if(! a)return c==0;
vector<int> num;
while(a) num.push_back(a % 10),a /= 10;
int n = num.size(a);int ans = 0,last = 0;// The number of answers, the number of occurrences of the prefix c
// The answer is in the 1-n-1 digits
for(int i = 1; i < n; i++)
for(intj = i ! =1; j < N; j++)
ans += f[i][j][c];
// The answer in n digits
for(int i = n - 1; i >= 0; i--)
{
int x = num[i];
// Take 0 to x - 1
// The number of occurrences of the suffix c
for(int v = (i == n - 1); v < x; v ++)
ans += f[i+1][v][c];
// The number of additional contributions to include c in the prefix x
ans += last * x * pow(10,i);
last += c == x;
// select all x values
if(i == 0) ans += last;// The number of c in the upper limit a
}
return ans;
}
int main(a)
{
int a,b;
dp(a);while(scanf("%d%d",&a,&b),a || b)
{
if(a > b) swap(a,b);// There are inversions in the input
for(int k = 0; k < N; k++)
cout << count(b,k) - count(a - 1,k) << ""; cout << endl; }}Copy the codeGeneral template
For digital DP problems, we have a generic code template that allows you to quickly frame your thinking for unfamiliar digital DP problems. The code is as follows:
int dp[N][N];/ / state
void dp(a) // Use dynamic programming to complete initialization
{}int count(int a)// Select a from [0,a]
{
// Boundary special judgment
if(! n)return___.// Unpack
vector<int> num;
while(a) num.push_back(a % 10),a /= 10;
int ans = 0;// Record the number of answers
int last = 0;// Record the historical information of the traversal
// Traverses the upper limit from high to low
for(int i = num.size() - 1; i >= 0)
{
/ / count
ans += ___ ;
if( ___ )
last++;
}
return ans;
}
int solve(int a,int b)
{
dp();
return count(b) - count(a - 1);
}
Copy the codeThank you for yxc && www.acwing.com/solution/co…