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 code

Topic 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 code

The 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 code

Step 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 code

And 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 code

The 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 code

At 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 code

General 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 code

Thank you for yxc && www.acwing.com/solution/co…