Digit DP

Counting by Digits · Tight & Loose · Memoize

1:00

How to count numbers in a huge range that satisfy a digit property by building candidates digit by digit with a tight-constraint flag and memoization.

By the end, you can

Explain why a brute-force loop fails for ranges up to 10^18 and how Digit DP avoids it.
Apply the f(R) − f(L−1) prefix trick to convert a range query into two prefix counts.
Trace the tight/loose transition rule for any sequence of digit choices.
Identify the three components of the Digit DP state and explain the role of each.
Write or read a Digit DP recursion, correctly computing the cap and propagating the tight flag.
Explain why only loose states are cached and construct the correct memo-table key.
Diagnose the three classic bugs: missing tight flag, missing started flag, and off-by-one in range subtraction.

Up next in String Algorithms, Advanced DP & Competitive Techniques