digit DP
Some counting problems ask 'how many numbers from 0 up to N have property P?' — for example, how many integers below a billion have no digit '7', or whose digits sum to a multiple of 3. N can be enormous (hundreds of digits), so you cannot loop over every number one by one. Digit DP is the technique for counting such numbers by building them one digit at a time, from the most significant digit to the least, and remembering just enough about the prefix to know whether property P can still be satisfied.
You process the digits of N left to right and, at each position, you decide which digit to place. The state carries a few pieces of information. The crucial flag is 'tight': are the digits chosen so far exactly equal to N's prefix? If tight is true, the next digit cannot exceed N's digit at this position (otherwise you would exceed N); if tight is false (you already placed something smaller), the next digit can be anything from 0 to 9 freely. Alongside tight you store whatever property P needs — a running digit sum modulo something, a count, the last digit, a 'have we seen a nonzero digit yet' leading-zero flag, and so on. Define dp[pos][tight][...other state...] as the count of valid ways to fill positions pos..end. The transition loops the digit d over its allowed range (0..9 if not tight, 0..N[pos] if tight) and recurses to pos+1 with tight updated (stays tight only if you placed exactly N's digit). Memoize on (pos, the property state) for the not-tight case, since the tight case happens at most once per position.
If N has L digits, there are about L positions times (a small property state) times 2 for tight, and each tries 10 digits, so digit DP runs in time roughly proportional to L times the property-state size times 10 — polynomial in the number of digits even though N itself is astronomically large. That is the whole point: it converts 'count up to 10^L' into work proportional to L. The classic gotchas are the leading-zero handling (a number like 007 is really 7, so a 'started' flag often matters) and answering range queries [A, B] by computing f(B) - f(A-1), where f(x) counts valid numbers in [0, x].
Count integers in [0, 325] with digit sum divisible by 3. State (pos, sum mod 3, tight). At the top, leading digit can be 0,1,2 (free, tight becomes false) or 3 (tight stays true). Each free branch then counts all completions whose remaining digit sum hits the right residue; the tight branch is forced to follow 3,2,5. Summing the branches gives the count without listing all 326 numbers.
Build the number digit by digit; the 'tight' flag enforces the upper bound N.
The 'tight' flag is what bounds you by N; forget it and you count over all L-digit strings instead. And for a range [A, B] you compute f(B) - f(A-1), so handle the off-by-one at A carefully.