Digit DP refers to a DP technique that solves problems that involve digits. The general style of said problems are: How many integers in the range from [L, R] satisfy some condition. Notice that L, R will always be huge (L,R <= 1e18) in order to prevent naive looping. To solve these problems, we need to perform digit dynamic programming.
Firstly, when we solve for a range [L,R], we really only need to solve for the range [0, R] and [0, L-1], then find the difference. Hence from now on we assume L = 0.
To solve these problems, we build the answer from left to right (from most significant digit to least significant digit).
We also need to make sure that we don’t exceed the upper limit.
Hence our state will be:
dp[i][j][….] where we have processed the first i digits, j is a boolean denoting whether or not we are already less than R, or we are still matching with R.
Here is an example of the dimension j:
Assume R = 12341
If our current built number is 12xxx, we are currently matching R in terms of value, so our next digit must be less than or equal to 3. If we build 124xx, then it is invalid since it is larger than R.
Now, what if we store 122xx. Then no matter what the last 2 digits are we will be less than R, so we can make it equal to any digit we want. Hence j is a boolean storing whether or not we are smaller than R for sure, or we are still matching R.
The state for this problem is
dp[i][j][k][l][m][n] -> ith position, j is equal to the last digit, k is the longest run, l is the current run, m is a boolean declaring whether or not we are less than the right bound, n is whether or not we have encountered a non zero digit yet (in order to ignore leading zeroes).