DIGIT DYNAMIC PROGRAMMING

Digit DP

Digit Dp is a very easy but most elegant and quite visible paradigm in Competitive Programming. In this post, I will be explaining the Digit DP , with an example.
And ofcourse as the name suggest, it deals with DP involving numbers in which you want certain specifications for a number :P Many a times a combinatorical solution also exist for such problems, which is harder to think, here I will be discussing DP solution which is easy to think of and implement once known. :D

Question - Find the count of numbers between x and y, such that distinct non-zero digits in them is less than 3. Source - Classy Numbers

Motivation

It would have been very easy to solve the question if there exist a function like F(x) which would solve the query for a given x, then our answer would be simply F(y) - F(x-1) .

Starters xD

Let’s initially suppose that no condition is imposed on numbers,m then how to count the numbers.
Let’s give this a shot
Let the digits of x be stored in num[], size be n(say). Let’s fill the digits from left to right in num, now how many digits can be placed at a certain place ??
Answer is simple if the number so formed is already smaller then we can use any of 0 to 9 digits at a place , if not then we can fill from 0 to num[i] at that place.

Moving On (The most Important Step..DP formulation)

Let the sequence of digits are stored in seq.

As we can see it is very easily observed that without conditions, only two states the pos, and check variable are required.
Wait!!! What are they ??
Pos represnts the position at which we going to fill any digit
Check represents a bool variable to know if the number has already became less or not.
Obviously afer multiplying the respective possible cnts of digits in a certain position , we can determne the total numbers formed.
Not actually multiplying, but that’s the beauty of DP, that it will add the possible numbers one by one easily. Confused ??? Check out the sample code, it will become too easy to understand then :)

A Bit More Explanation

Let’s say during the building of the sequence, currently we are at position pos. We have already placed some digits in position from 1 to pos-1. So now we are trying to place a digit at current position pos. If we knew the whole sequence we have build so far till position pos-1 then we could easily find out which digits we can place now. But how?

You can see that, in the sequence seq the left most digit is actually the most significant digit. And the significance get decreased from left to right. So if there exist any position t (1 <= t < pos) where seq[t] < num[t] then we can place any digit in our current position. Because the sequence has already become smaller than x no matter which digit we place in the later positions. Note, num[t] means the digit at position t at number x .

But if there was no t that satisfy that condition then at position pos, we can’t place any digit greater than num[pos]. Because then the number will become larger than b.

Final Battle - The conditions

It is very easy to implement the conditions, as soon as one introduce a condition a new state has to be made , just simple (of course we may optimize further in some cases).
Coming back to Classy Numbers now, the given condition is that number of non- zero digits must be less than or equal to 3.
Therefore a new state in DP, thats the cnt..
Now, is anything left ?? Just write it down.

Extras :)
Do you need more questions ?


   #define ll long long int
   ll n,m,i,j,k;
   vector num;
   ll dp[20][10][2];

   // dp[i][j][k]-- i represents position, j represents cnt, k represents whether the number has already became smaller or not. If smaller then k=1 else k=0.

   ll call(ll pos,ll cnt,ll f)
   {
     if(cnt>3)
      return 0;
    if(pos==num.size())
    {
      if(cnt<=3)
        return 1;
      else
        return 0;
    }
    
    if(dp[pos][cnt][f]!=-1)
      return dp[pos][cnt][f];
      
    ll res=0,limit,dig;
    
    if(f==0)
      limit= num[pos];
    else
      limit=9;
      
    for(dig=0;dig<=limit;dig++)
    {
      ll nf=f; // new checking condition
      ll ncnt=cnt; // new cnt
      
       if(f==0&&dig<limit) 
           nf=1;
       if(dig>0) 
           ncnt++;
       if(ncnt<=3) 
          res+=call(pos+1,ncnt,nf);
    }
    
    return dp[pos][cnt][f]=res;
   }

   ll solve(ll n)	
   {
     num.clear(); //Storing  the digits in num and then afterwards reversing to get the num in proper order.
     
     while(n>0)
     {
      num.pb(n%10);
      n/=10;
     }
     
     reverse(num.begin(),num.end());
     memset(dp,-1,sizeof(dp));
     ll res=call(0,0,0);
     return res;
     
   }

    int main()
    {   
         ll t;
         cin>>t;
         while(t--)
         {
         cin>>n>>m;
         cout<< solve( m )-solve( n-1 )<< endl;
         }
         return 0;
    }

</pre>