Digit Dynamic Programming

Digit Dynamic programming is a technique of applying Dynamic Programming on digits of numbers. This blog post assumes that the reader is already familiar with dynamic programming.

This technique usually involves with problems that requires finding the amount of numbers with a specific property in a given range.

Sample Problem

Find the amount of integers in the range \([0,a]\) , where the sum of digits is \(k\)

We will build a number with \(\lfloor \log_{10} ( a) \rfloor + 1\), Number of digits of \(a\) ( ref).  Start from the most significant digit (left side) and gradually reach the right completing digits.

When using Dynamic Programming to solve this problem, We will keep some data on the state, and the value stored will be the amount of numbers that can be created by the way described by the state.

What should be on the state?

The amount of digits we have already picked has to be on the state. At each step we have 10 choices for digits to place. But choosing some digit may lead the constructed number to be greater than \(a\). If there is some \( i < \text{current pos}\) such that the \(i^\text{th}\) digit of \(a\) is greater than the \(i^\text{th}\) digit of the constructed number, then whatever we place next won't make the constructed number bigger than \(a\). Then we should keep whether this happend in the state. State so far is fairly common for all digit dp problems. For this specific problem we will keep the current sum of the partially constructed number. (Like in the Knapsack problem)

State

• Amount of digits that have been analyzed
• Whether number is less than the target irrespective of next placements
• Current Sum of the constructed number (Problem specific)

Transitions

Let \(f\) be the state that the number is less than the target irrespective of next placements

current state \(f,\text{index},\text{sum}\)

if \(f\) is true,

• \(f,\text{index}+1,\text{sum}+k \text{ for all } k \text{ in } [0,9]\)

else,

• \((k<a_{\text{index}+1}),\text{index}+1,\text{sum}+k \text{ for all } k \text{ in } [0,a_{\text{index}+1}]\)

Note: In this problem we have found the answer for the range \([0,a]\). To find the answer for a range \([a,b]\),

\(\text{let the answer for the range} [a,b] = f_{a,b} \)

\(f_{a,b}=f_{0,b}-f_{0,a-1}\)

Sample Code

long long solve(long long a, int k) {
    string a_string = to_string(a);
    int n = a_string.size();

    long long dp[n][k+1][2];
    memset(dp, 0, sizeof(dp));

    for (int i=0; i<n-1; i++) {
        for (int sum=0; sum<=k; sum++) {
            for (int f=0; f<=1; f++) {
                
                for (int j=0; j<=(f?9:(a_string[i+1]-'0')); j++) {
                    if (sum + j <= k) // filtering out unwanted states
                        dp[i+1][sum+j][f || j<(a_string[i+1]-'0')] += dp[i][sum][f];
                }

            }
        }
    }

    return dp[n-1][k][0] + dp[n-1][k][1];
}