Advanced DP

Voucher numbers you can read over the phone

Gift voucher numbers get read aloud on support calls, and on a bad line several digits sound alike. So the numbers use only 1, 3, 5 and 7, and the system caps them at 4,000,000,000. How many vouchers can be issued? And if 9 is allowed too? And if the cap goes to ten billion?

The obvious answer is a loop: go through every number up to the cap, check its digits, and count the ones that pass. A laptop checks about two million numbers a second. Do the sum before reading on. Four billion numbers take over half an hour, for one version of the question, and there are already three versions to answer.

Look at the cap instead: 4,000,000,000 has ten digits. Any ten-digit voucher that starts with 1 or 3 is already below the cap, whatever its other nine digits are. Only a voucher that starts with 4 would still have to be compared with the cap, and 4 is not an allowed digit. So the useful question to ask about each prefix is: in how many ways can it be finished?

Pause and predict A voucher's first digit is 1, so it is already below the cap. How many ways are there to fill its other nine digits?

Count the ways a prefix can finish

How many numbers from 1 to N use only the digits 1, 3 and 5? How many have no repeated digit? How many ones are written in all the numbers from 0 to N? With N up to 10⁹, a loop is too slow. It also repeats work: once a prefix is smaller than N's prefix of the same length, the remaining digits can be anything allowed, so every such prefix has the same choices left.

So walk through the digits of N from the left. Pad every number to N's length with leading zeros, so that 7 becomes 007 when N = 352. Each number is then a path of digit choices, and the question at each step is: from this prefix, how many ways are there to finish the number?

This is called a digit DP. Why does the walk count each number exactly once? Take any number x below N, padded with leading zeros. Reading from the left, x matches N for some digits, then has a smaller digit at one position, the first place where they differ. Before that position, x's prefix is tight; from that position on, it is free. The walk follows N's own digits and, at each position, also branches off with every smaller digit. Every x branches off at exactly one position, with exactly one digit, so it is counted once. N itself never branches off; it is counted at the end if all its digits are allowed.

The two flags

The tight flag enforces the upper bound N. While the prefix is tight, the next digit may go up to N's digit at that position, and only N's digit keeps the prefix tight. Once the prefix is free, the next digit may go up to 9. Without the flag, the walk counts numbers above N.

The started flag deals with the padding. A leading zero is not a real digit of the number. If the property looks at the digits (only 1, 3 and 5, or no repeated digit), the padding zeros of 007 must be ignored. When a leading zero would change nothing, as when you count ones, you can leave this flag out.

Pause and predict Numbers up to 352 using only 1, 3 and 5. The right count is 28. Drop the tight flag: what does the walk count?

The state is what the future needs

As in Unit 18, ask what the rest of the number needs to know about the prefix. For a set of allowed digits, it needs nothing, because every allowed prefix leaves the same choices. For no repeated digit, it needs the set of digits already used, stored as a 10-bit mask. For counting ones, it needs the number of ones so far. Two free prefixes with the same state have the same ways to finish, which is why memoisation reduces billions of numbers to a few thousand cells.

Only free states need the memo. There is just one tight prefix per position, N's own, so storing its answer saves nothing. Storing it in the same cell as the free states would also be wrong, because the tight prefix has fewer ways to finish.

When the state is empty, the free cells have a formula. With k allowed digits and r positions left, f = kʳ. Numbers At Most N Given Digit Set then becomes two sums. The first counts the shorter numbers: k + k² + ... + k^(L-1), where L is the number of digits in N. The second follows the tight path: at each position it adds (the number of allowed digits below N's digit) · k^(positions remaining), and it stops if N's digit itself is not allowed.

Sets: the state is which items are covered

Unit 22 introduced states that hold a set. Two problems here take the idea further. In Smallest Sufficient Team, two teams that cover the same skills can be completed in the same ways, so the state is the mask of skills covered: dp[mask] is a smallest team that covers exactly the skills in mask. With 16 skills there are 65,536 masks, compared with 2⁶⁰ possible sets of people. Adding a person can only add bits to the mask, so filling the masks in increasing numeric order is a valid order. Store the team itself, or a pointer to the previous mask, because the question asks which people are in the team.

Find the Shortest Superstring uses the travelling salesman table from Unit 22. The words play the role of cities, and placing word b right after word a saves as many letters as they overlap. The saving for the next word depends on the last word placed, so the state is dp[mask][last]: the most letters saved by a chain that uses exactly the words in mask and ends with the word last.

A polygon: the interval DP again

Minimum Score Triangulation has the same shape as Burst Balloons. The edge from corner i to corner j belongs to exactly one triangle, and that triangle's third corner k splits the polygon into two smaller polygons that do not affect each other. So dp[i][j] = min over k of dp[i][k] + v[i]·v[k]·v[j] + dp[k][j], filled in order of increasing gap j - i.

A median: binary search on a cut

Median of Two Sorted Arrays is solved with binary search; it is in this unit because it is one of the hard problems. In Unit 6, the search looked for the boundary between false and true. Here it looks for a cut: how many numbers the shorter array contributes to the left half of all the numbers. The other array must contribute the rest, so that one number determines the whole cut.

Pause and predict At the current cut, a[i - 1] > b[j]. Which way must the cut in array a move?

How to recognise it

If a problem asks you to count the numbers from 1 to N that meet a condition on their digits, and N is far too big to loop over, use a digit DP. If it asks for the fewest items that together cover a set of at most about 16 to 20 things, use a mask over the things to cover. If it asks for the shortest result that includes every word, use the travelling salesman table. If it gives two sorted arrays and asks for a logarithmic time bound, binary search for a cut.

Pause and predict How many numbers from 1 to 10¹² have no two equal neighbouring digits?

Problems that only look like it

• A question about the bits of one number, or one with a closed formula, such as raising a number to a power. These are in Unit 23. Digit DP counts over all numbers up to a bound.
• A request to list every team or every order. The output itself can be exponentially long, so it needs backtracking. A count or a smallest size over a small set fits a mask table.
• Ranges with a split point, a tree, or visiting every node of a graph with n ≤ 12. The basic versions are in Unit 22. This unit adds the digit walk and covering problems.
• A value that can be checked with a yes or no test, such as "the smallest speed that finishes in time". That is binary search on the answer, from Unit 6. The median search looks for a position in one array and checks it against the other.

Where it bites

Pause and predict Java: a team of people stored as bits in an int. What is 1 << 40?

• Forgetting the tight flag. Every position then goes up to 9 and numbers above N are counted: 39 instead of 28 for {1, 3, 5} up to 352.
• Letting a free prefix become tight again. The new tight value must be tight AND d == limit. Testing only d == 9 puts the cap back on a prefix that was already free. For numbers with all digits different up to 100, that gives 82 instead of 90.
• Letting leading zeros into the state. 7 is walked as 007, and a mask of used digits must not include those zeros. Count the number 0 only if the question includes it.
• Storing tight states in the same memo cells as free ones. The tight prefix has fewer ways to finish. Key the memo on the whole state, or store only free states.
• Covering greedily. Picking the person with the most new skills, or joining the pair of words with the biggest overlap, can both give a worse answer; the tests in this unit's problems include one case of each.
• Searching for the cut in the longer array. Then j = half - i can fall outside the other array. Swap the arrays so the search runs over the shorter one.