How Digit DP works?

Revision en1, by ParshuParishram, 2021-09-10 11:23:43

Suppose you are given following problem:

Problem Statement: Find the count of numbers between L to R which have sum of digits = x
where, $$$1 \le L \le R \le 10^{18}$$$ and $$$1\le x\le 100$$$

Naive Solution: Check each of the number satisfying the condition and increment the count

Digit DP Solution:
Lets denote the count from L to R as $$$f(L,R)$$$
Then, the problem can be again rewritten as $$$f(L,R) = f(0,R) - f(0,L-1)$$$

Now the problem is to find $$$f(0,R)$$$ for any R
From the constraints of the problem statement you might have guessed that one of the dp states would be the sum of digits i.e. $$$x$$$ but what is the second state?
Its the number of digits!!
For now lets forget about the constraint that the numbers should be $$$\le R$$$
Just think we have upto $$$N$$$ digits and sum of digits should be $$$x$$$. And count that!

$$$dp[N][x]$$$ denotes the count of numbers which have sum of digits $$$=x$$$ and number of digits $$$\le N$$$
Then, $$$dp[N][x] = \sum_{k=0}^{9} dp[N-1][x-k]$$$

All good??
Alright! Moving ahead!

Now, this dp counts the number without the constraint $$$\le R$$$.
Suppose $$$R = 4258$$$ and $$$x=11$$$
Then, we should not count $$$4430$$$ because $$$4430\ge 4258$$$, but how our dp will know we are exceeding R?

We can include one more state or two $$$dp$$$ arrays $$$dp_1$$$ and $$$dp_2$$$
$$$dp_1[N][x] = $$$ count of the numbers under tight constraint
$$$dp_2[N][x] = $$$ count of the numbers with no constraint as such (so $$$dp_2$$$ will behave as it is we discussed above)

Now you may be asking what is tight constraint?
Ans: at the $$$N^{th}$$$ digit we will check if this digit is less or equal to the $$$N^{th}$$$ of $$$R$$$
Denote $$$R_N$$$ as Nth digit of R,
Then, $$$dp_1[N][x] = dp_1[N-1][x-R_N] + \sum_{k=0}^{R_N-1} dp_2[N-1][x-k]$$$

And, for $$$dp_2$$$ its already unconstrained so its chill there :)
$$$dp_2[N][x] = \sum_{k=0}^{9} dp_2[N-1][x-k]$$$

Tags #dp, #digitdp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ParshuParishram 2021-09-11 16:50:15 9 Tiny change: '[x-k]$\n\n' -> '[x-k]$\n\n\n\n<hr/>'
en3 English ParshuParishram 2021-09-10 11:45:28 298 (published)
en2 English ParshuParishram 2021-09-10 11:44:29 302 Tiny change: ' in $L-1$ **But wait' -> ' in $L-1$ <br/>\n**But wait' (saved to drafts)
en1 English ParshuParishram 2021-09-10 11:23:43 1973 Initial revision (published)