Digit Dynamic Programming (Digit DP) - Preparation to IOI Part 5
Digit Dynamic Programming (Digit DP)
Digit Dynamic Programming (Digit DP)
Introduction
Many problems ask us to count integers whose decimal representation satisfies some condition. For example, we may need numbers whose digit sum is equal to a given value, numbers divisible by m, numbers with exactly k nonzero digits, or numbers that do not contain two equal adjacent digits.
If the range is small, we can inspect every number. However, digit problems often use bounds such as 1018 or even a number given as a string with hundreds of digits. Iterating through the range is then impossible.
Digit DP solves this by constructing the number one digit at a time. Instead of remembering the whole prefix, we remember only the information about that prefix that can affect future choices. We also remember whether the prefix is still equal to the prefix of the upper bound. This lets us count a huge set of numbers using a small number of states.
Problem or motivation
We will use the following problem throughout the lecture.
Given integers L, , and , count the integers such that:
R
S
x
L≤x≤R;
the sum of the decimal digits of x is exactly S.
Assume that 0≤L≤R≤1018 and 0≤S≤171.
For example, in the range [10,25], the numbers with digit sum 5 are 14 and 23, so the answer is 2.
Core concept
First count a prefix range
It is easier to count valid numbers in [0,X] than directly in [L,R]. Define calc(X) as the number of valid integers in [0,X].
Then the required answer is calc(R)−calc(L−1).
This subtraction removes every valid number smaller than L. We define calc(X)=0 when X<0, which also handles the case L=0.
Construct numbers from left to right
Write X as an array of digits. If X=325, we process the hundreds digit, then the tens digit, then the units digit.
We build every number using exactly the same number of positions as X. Shorter numbers are padded with leading zeros. For example, while counting up to 325, the number 47 is represented as 047. This does not change its digit sum, and every integer still has exactly one representation.
At each position, we choose one digit. The important question is how large that digit is allowed to be.
The tight flag
We use a Boolean value tight.
tight=true means the chosen prefix is exactly equal to the corresponding prefix of X. The current digit cannot exceed the current digit of X.
tight=false means the chosen prefix is already smaller than the prefix of X. The remaining digits may be anything from 0 to 9.
For example, let X=325.
After choosing the first digit 3, the prefix is still equal, so tight remains true and the next digit is at most 2.
After choosing the first digit 1, the constructed number is already smaller than 325. No future suffix can make it too large, so every later digit may be from 0 to 9.
Choosing a first digit larger than 3 is not allowed.
The invariant is simple: every prefix reached by the DP can still be completed into a number not greater than X.
The DP state
For the digit-sum problem, define get(pos,sum,tight) as the number of ways to fill all positions starting from pos, where:
pos is the next digit position to choose;
sum is the sum of all digits chosen before this position;
tight tells us whether the chosen prefix is still equal to the prefix of X.
This state contains everything the future needs to know. It does not matter which exact digits created sum; only the current sum, position, and relation to the bound affect the remaining choices.
This is the central question when designing any Digit DP: what information about the prefix can change which suffixes are valid? Store exactly that information in the state.
Main algorithm
Suppose the current state is get(pos,sum,tight).
If tight is true, the largest allowed digit is the digit of X at position pos. Otherwise, the largest allowed digit is 9. We try every digit from 0 to this limit.
After choosing digit:
the next position is pos+1;
the new digit sum is sum+digit;
the next state remains tight only if the old state was tight and digit is equal to the current bound digit.
If the chosen digit is smaller than the bound digit while tight is true, the new prefix becomes smaller and next_tight becomes false. Once it becomes false, it never becomes true again.
When all positions have been processed, there is exactly one constructed number. We return 1 if its digit sum is S, and 0 otherwise. A state with sum>S can return 0 immediately because adding more nonnegative digits can never reduce the sum.
We memoize the result of every state. The bound digits are fixed during one call of calc(X), so equal states always have equal answers. Before calculating another bound, we clear the memoization table.
Algorithm:
Leading zeros and the started flag
Leading zeros are harmless for digit sum: the padded representation 047 has the same digit sum as 47. They are also harmless for a remainder modulo m, because starting with zeros does not change the represented value.
They are not harmless for every condition. Suppose we want to count numbers containing exactly one zero digit. The number 47 may be represented as 047 while processing a three-digit bound, but its leading zero is not part of its usual decimal representation and must not be counted. Similar problems appear when we track the number of digits, the first digit, or adjacent digits.
For such conditions, add a Boolean state started:
if started=false and we choose digit 0, the number has still not started; this is only padding, so digit-dependent information is not updated;
if started=false and we choose a nonzero digit, the number starts at this position;
once started=true, every chosen digit, including zero, is a real digit.
The path that never starts represents the number 0. At the base case, decide explicitly whether 0 should be counted and how its decimal representation should be interpreted. This convention depends on the problem.
For an adjacency condition, we may store last_digit together with started. We compare the new digit with last_digit only after the number has started. This prevents padding zeros from behaving like real adjacent digits.
Some common state extensions are:
Condition
Extra state
Update after choosing digit
Digit sum
sum
sum+digit
Value modulo m
remainder
(remainder⋅10+digit)modm
Exactly k nonzero digits
count
count+[digit=0]
No equal adjacent digits
last_digit, started
reject a real digit equal to last_digit
A digit has appeared
found
found∨(digit=wanted_digit)
A forbidden pattern is absent
state
follow the automaton transition for digit
The position and bound flag remain the same. Only the part of the state describing the condition changes.
Implementation
Complexity
Let D be the number of digits and let S be the target digit sum.
Time:O(D⋅S⋅10)
Memory:O(D⋅S)
The constant factor for the two values of tight is omitted.
1. Define get(pos, sum, tight):
1.1. If sum > S, return 0.
1.2. If pos is past the last digit:
- return 1 if sum = S;
- otherwise return 0.
1.3. If this state was already calculated, return its stored answer.
1.4. If tight = true, set limit to bound_digit[pos].
Otherwise, set limit to 9.
1.5. Set res = 0.
1.6. For every digit from 0 to limit:
- next_tight = tight and (digit = bound_digit[pos]);
- add get(pos + 1, sum + digit, next_tight) to res.
1.7. Store and return res.
2. Define calc(X):
2.1. If X < 0, return 0.
2.2. Convert X to its decimal digit string.
2.3. Clear the memoization table.
2.4. Return get(0, 0, true).
3. Return calc(R) - calc(L - 1).
#include <bits/stdc++.h>using namespace std;const int N = 20;const int M = 200;long long dp[N][M][2];bool used[N][M][2];string bound_digits;int target_sum;long long get(int pos, int sum, int tight){ if(sum > target_sum){ return 0;} if(pos ==(int)bound_digits.size()){ return sum == target_sum;} if(used[pos][sum][tight]){ return dp[pos][sum][tight];} used[pos][sum][tight] = true; int limit = 9; if(tight){ limit = bound_digits[pos] - '0';} long long res = 0; for(int digit = 0; digit <= limit; digit++){ int next_tight = tight &&(digit == bound_digits[pos] - '0'); res += get(pos + 1, sum + digit, next_tight);} dp[pos][sum][tight] = res; return res;}long long calc(long long x){ if(x < 0){ return 0;} bound_digits = to_string(x); memset(used, false, sizeof(used)); return get(0, 0, true);}int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); long long l, r; cin >> l >> r >> target_sum; cout << calc(r) - calc(l - 1)<< endl; return 0;}