Lesson 14 · Problem-solving methods

Digit Dynamic Programming

Digit DP counts numbers within a bound by processing digits left to right while tracking whether the constructed prefix is still tight to that bound.

Counting without enumerating numbers

Many queries ask how many integers up to X satisfy a digit property: digit sum, forbidden pattern, remainder, or repeated digits. Enumerating X values is impossible when X has dozens of digits, but the number of distinct prefix states is small.

Process the decimal representation from most significant to least. A state typically contains position, tight, started, and property-specific data such as sum or modulus. Memoize only information that determines all legal suffixes.

Work over the bound’s digit string
Prefix summaries define states
State count depends on digits, not X

The tight flag

Tight is true when the chosen prefix equals X’s prefix. The next digit may then be at most X[position]. Choosing less makes tight false permanently; choosing equal preserves it. When tight is false, every digit 0–9 is legal.

Using the original bound digit after tight has become false undercounts. Conversely, allowing 9 while tight and the bound digit is smaller counts values above X. The update is newTight=tight && digit==limitDigit.

Tight means prefix equality
Smaller choices release the bound
The flag never becomes true again

Key reference

Terms, operations, and practical uses

Bound state

PositionPosition is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Tight flagTight flag is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Digit limitDigit limit is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Property state

Leading zeroLeading zero is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Started flagStarted flag is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Digit sumDigit sum is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Range counting

Count up to RCount up to R is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Subtract L-1Subtract L-1 is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Loose-state cacheLoose-state cache is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Digit DP counts values with digit sum 3

from functools import lru_cache
digits=list(map(int,str(25)))
@lru_cache(None)
def dp(pos,total,tight):
    if pos==len(digits):return int(total==3)
    limit=digits[pos] if tight else 9;ans=0
    for d in range(limit+1):ans+=dp(pos+1,total+d,tight and d==limit)
    return ans
print("Count:",dp(0,0,True))

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
string bound="25";
int memo[3][30][2];
int solve(int pos,int sum,bool tight) {
    if(pos==(int)bound.size()) return sum==3;
    int &ans=memo[pos][sum][tight];
    if(ans!=-1) return ans;
    ans=0;
    int limit=tight?bound[pos]-'0':9;
    for(int d=0;d<=limit;d++) ans+=solve(pos+1,sum+d,tight&&d==limit);
    return ans;
}
int main() {
    memset(memo,-1,sizeof memo);
    cout << "Count: " << solve(0,0,true) << '\n';
}

import java.util.*;
class Main {
    static String bound="25";
    static Integer[][][] memo=new Integer[3][30][2];
    static int solve(int pos,int sum,int tight) {
        if(pos==bound.length()) return sum==3?1:0;
        if(memo[pos][sum][tight]!=null) return memo[pos][sum][tight];
        int ans=0,limit=tight==1?bound.charAt(pos)-'0':9;
        for(int d=0;d<=limit;d++) ans+=solve(pos+1,sum+d,tight==1&&d==limit?1:0);
        return memo[pos][sum][tight]=ans;
    }
    public static void main(String[] args) {
        System.out.println("Count: "+solve(0,0,1));
    }
}

Watch it run

Step through it

Running on 0 through 25

Output

Leading zeros and the started flag

Padding shorter numbers with leading zeros makes all candidates share the bound length. Started distinguishes padding from real digits so properties such as digit count, zero occurrence, and adjacent equality are interpreted correctly.

Decide how the number zero is represented. If no nonzero digit was chosen at the base case, the candidate may represent zero once, or may be excluded when counting positive integers. This is an API decision, not an implementation accident.

Padding unifies lengths
Started prevents fake leading digits
Define whether zero counts

Memoization and ranges

States with tight=false are independent of X’s remaining prefix and are highly reusable. Tight states depend on the bound path and are few; caching all states with tight included is also correct. Complexity is positions times state combinations times ten transitions.

To count [L,R], compute F(R)−F(L−1). Handle L=0 without forming a negative digit string. For a modulus state, update (old*10+digit)%m; for digit sum, bound the sum by 9·digits.

Loose suffix states are reusable
Subtract prefix counts for ranges
Property state updates per digit

Testing and state explosions

Compare every bound up to a few thousand with brute force. Test powers of ten, all-nines bounds, zero, leading-zero-sensitive properties, and L=R. Off-by-one errors cluster at digit-length transitions such as 99 to 100.

Do not add history to the state unless future legality needs it. Pattern restrictions can store an automaton state instead of the entire prefix, keeping the DP finite and composable.

Brute-force small bounds
Powers of ten expose boundaries
Automata compress pattern history

Scaling property states

A digit automaton can track forbidden substrings, occurrence counts, or alternating patterns while the DP supplies position and tightness. Product states combine an automaton with a modulus or digit sum, but their counts multiply; calculate the state-space product before coding.

For many bounds with equal digit length, precompute loose suffix transitions and reuse them. When the modulus is large or several statistics are tracked, sparse memoization may visit far fewer states than a dense array. Cache keys must still distinguish started when leading padding changes property semantics.

Memo tables are bound-specific when tight states are cached without the bound in the key. Clear them between unrelated bounds or cache only loose states. Range subtraction should use a result type large enough for the total count and normalize only when the problem explicitly requests a modulus.

Digit DP counts representations, so the chosen representation must be unique. Fixed-width padding with leading zeros is safe only when the started flag makes 007 semantically identical to 7 for the property being tested. To exclude zero, handle the terminal state where started is still false. For base B, replace decimal limits and transitions with 0 through B−1; the state design is otherwise unchanged. Complexity is positions multiplied by every property-state dimension, the two tight values, and up to B outgoing digit choices. State this product explicitly because a small number of digits can still hide an oversized modulus or automaton dimension.

Automata summarize pattern history
State dimensions multiply
Loose suffixes can be precomputed