vault

Digit DP

23 min read

Digit DP

Digit DP is the umbrella name for a family of dynamic-programming techniques designed to count (or sum, or compute statistics over) integers in a range [L, R] satisfying some digit-related property P. The property typically depends on the number’s individual digits — the count of a particular digit, the sum of digits, divisibility, the presence/absence of a substring of digits, equality to a palindrome, or any other constraint expressible position-by-position. Naively iterating over [L, R] is Θ(R − L), fine for R = 10^6 but disastrous for R = 10^{18}. Digit DP decomposes the problem digit-by-digit, building integers one position at a time while tracking three pieces of state: (1) the position in the number being built, (2) a “tight” flag indicating whether the prefix so far is still equal to the corresponding prefix of R (the upper bound), and (3) any auxiliary state the property P requires (digit-sum-modulo-k, last digit, count of a specific digit, etc.). The complexity is typically O(d · S · 10) where d = ⌊log₁₀(R)⌋ + 1 is the number of digits and S is the size of the auxiliary state — utterly polynomial in log R rather than linear in R. The technique is mostly seen in competitive programming (Codeforces, AtCoder, ICPC) and shows up in advanced LeetCode problems (LC 233, LC 600, LC 902, LC 1067, LC 2376, LC 2719). The conceptual hook is the tight flag: once the prefix has gone “below” the upper bound at any position, all subsequent digits are unconstrained and can be 0–9 freely; until then, the current digit is constrained to 0..R’s-digit-at-this-position, and choosing exactly that digit keeps the tight flag set. Mastering this single-bit state-machine is the difference between a solution that runs in milliseconds and a brute force that doesn’t terminate.

1. Intuition — Build the Number Digit-by-Digit, From the Most-Significant End

Suppose R = 4567 and you want to count numbers in [0, R] with some property P (e.g., “digit sum is a multiple of 3”). The naive iteration over 4568 numbers is fine here, but if R = 10^{18} it is not. Digit DP says: instead of generating numbers, generate them digit-by-digit, from the most significant to the least significant, and track enough state to know how many ways the remaining digits can be filled to satisfy P.

The first decision is “what’s the leading digit?” If R = 4567, the first digit can be 0, 1, 2, 3, 4. If we pick 0, 1, 2, or 3, then the remaining three digits can be anything (000 to 999) and we are no longer constrained by R. If we pick 4, then the next digit is constrained: it can only be 0, 1, 2, 3, 4, 5 (because R’s next digit is 5). And so on, recursively.

This dichotomy — “are we still hugging the upper bound, or have we already gone strictly below?” — is captured by a single boolean state called the tight flag. When tight, the current position’s digit ranges over 0 to R_pos (the digit of R at this position). When not tight, it ranges freely over 0..9. Tightness can only break in one direction: once not-tight, always not-tight. This is what makes the state space tractable.

A real-world analogy: imagine you are reading off a budget cap of $4567 for a charity drive. As pledges come in, donors call out their pledges digit-by-digit (“first digit?”, “next digit?”). As long as everyone has pledged exactly the same digits as the cap so far, the auctioneer is still constraining the next digit (you can’t bid $5xxx because that exceeds the cap). The moment someone bids less than the cap’s digit at some position (say $3xxx), all subsequent digits are unrestricted — you’ve already saved enough to bid 999 and still be under cap. The “tight flag” is just whether the auction is still at the cap or has gone safely below.

The third piece — the auxiliary state — is whatever extra information the property P requires. For “digit sum mod 3 == 0”, you track the running sum mod 3 (state of size 3). For “no two consecutive digits are the same”, you track the previous digit (state of size 11, including a “no previous digit” sentinel). For “doesn’t contain the substring 13”, you track the last digit (state of size 11) plus a “have we seen 13 already?” flag (state of size 2). The auxiliary state’s size determines the complexity, and the art of digit DP is finding the minimal state that encodes everything you need to know.

The computation runs as a recursion over positions, with a memo keyed on (position, tight flag, auxiliary state). For typical problems, this gives O(d · 2 · S · 10) time, where d is the digit count, S is the auxiliary state cardinality, and 10 is the per-position branching factor. For R = 10^{18} and S = 100, that’s ~3.6 × 10^4 operations — essentially free.

2. The Tight-Flag Mechanics

The tight flag is the conceptual heart. Walk through it once and it’s permanently understood.

Let R = d_0 d_1 d_2 ... d_{n-1} be R written digit-by-digit, most significant first. We construct numbers x = x_0 x_1 ... x_{n-1} (also n digits, with leading zeros if x < 10^{n-1}) one digit at a time. At position i, we choose x_i.

The constraint: x ≤ R. Equivalently:

  • Either there exists some position j < i where x_j < d_j (and x_k = d_k for all k < j), in which case any choice of x_i is valid.
  • Or x_k = d_k for all k < i (we have been hugging R so far), in which case x_i ≤ d_i. If x_i < d_i, we go “below” and all subsequent positions are free. If x_i = d_i, we stay tight.

The tight flag at position i summarizes case 2 vs case 1: tight = 1 means we are still in case 2 (no position has yet “gone below”); tight = 0 means we are in case 1 (some prior position went below, all is free).

Transitions:

  • If tight = 0 (already free): x_i ∈ {0, 1, ..., 9}, and tight remains 0.
  • If tight = 1:
    • If x_i < d_i: tight flips to 0 for the next position.
    • If x_i = d_i: tight remains 1.
    • If x_i > d_i: invalid (would exceed R).

Equivalently: new_tight = tight AND (x_i == d_i). The tight flag can only flip from 1 to 0 across positions; never the other way.

This gives the DP its tractability: the tight dimension is just a single bit, doubling the state size by a factor of 2 — negligible. The position dimension is d ≈ log₁₀ R, and digit choices at each position are at most 10. The total work is dominated by the auxiliary-state size.

3. Worked Example — Count Integers in [0, N] With Digit Sum Equal to k

Concrete formulation: given N (up to 10^{18}) and k (up to ~200), count how many integers in [0, N] have digit sum exactly k.

3.1 State Design

  • Position pos: which digit we are filling (0-indexed from the most significant). pos ∈ [0, d] where d is the digit count of N.
  • Tight flag tight: 1 if the prefix equals N’s prefix, 0 otherwise.
  • Auxiliary state sum_so_far: the sum of digits placed so far, sum ∈ [0, k] (we can prune anything > k since the answer can’t recover).

State count: d × 2 × (k+1). For N = 10^{18}, k = 200: 19 × 2 × 201 ≈ 7600 states. Each transitions to at most 10 child states. Total work: ~76,000 — instant.

3.2 Recurrence

count(pos, tight, sum_so_far) = number of ways to fill positions pos, pos+1, ..., d-1 such that:

  • The remaining digits respect the tight constraint relative to N.
  • The total digit sum equals k.
count(pos, tight, sum_so_far):
    if pos == d:
        return 1 if sum_so_far == k else 0
    upper := digit_of_N_at_pos[pos] if tight else 9
    total := 0
    for digit in 0..upper:
        new_tight := tight and (digit == upper)
        new_sum := sum_so_far + digit
        if new_sum > k:                        # prune: sum can't decrease
            continue
        total += count(pos + 1, new_tight, new_sum)
    return total

Symbol-by-symbol unpacking:

  • pos is the current digit position (0-indexed from MSB).
  • tight is the tight flag at this position; if 1, we’re still hugging N; if 0, we’re free.
  • sum_so_far is the sum of digits already placed.
  • upper is the maximum allowed digit at this position: N’s digit if tight, 9 if not.
  • For each candidate digit, new_tight = tight AND (digit == upper) (the conjunction: both must be true to remain tight).
  • new_sum = sum_so_far + digit is the running total updated.
  • Recurse and sum.

3.3 Tiny Numerical Trace

N = 24, k = 6. Numbers in [0, 24] with digit sum = 6: let’s enumerate by hand: 06, 15, 24 → three numbers (treating 06 as 6 → digit sum 6, valid; 15 → 1+5=6; 24 → 2+4=6). So expected count = 3.

DP trace (N = 24, so d = 2, digits [2, 4], k = 6):

Start: count(pos=0, tight=1, sum=0).

At pos 0, tight, upper = 2. Try digit ∈ {0, 1, 2}:

  • digit = 0: new_tight = (1 AND 0 == 2) = (1 AND 0) = 0. new_sum = 0. Recurse count(1, 0, 0).
  • digit = 1: new_tight = (1 AND 1 == 2) = 0. new_sum = 1. Recurse count(1, 0, 1).
  • digit = 2: new_tight = (1 AND 2 == 2) = 1. new_sum = 2. Recurse count(1, 1, 2).

count(1, 0, 0): pos 1, free, sum 0. Upper = 9. Try digit ∈ {0, …, 9}:

  • We need final sum = 6. So digit must be 6.
  • digit = 6: new_sum = 6. Recurse count(2, 0, 6) → returns 1 (base case: sum == k). All other digits at this level give sum ≠ 6 → return 0.
  • Total: 1. (This corresponds to the number 06 = 6.)

count(1, 0, 1): pos 1, free, sum 1. Need digit = 5 to reach sum 6.

  • digit = 5: returns 1. (This is 15.)
  • Total: 1.

count(1, 1, 2): pos 1, tight, sum 2. Upper = 4 (digit of N at position 1). Try digit ∈ {0, …, 4}:

  • digit = 4: new_sum = 6. Returns 1. (This is 24.)
  • Other digits: sum ∈ {2, 3, 4, 5} ≠ 6, return 0.
  • Total: 1.

Sum at root: 1 + 1 + 1 = 3. ✓

The DP found exactly 3, matching the brute-force enumeration.

3.4 Memoization Subtlety

Memoization keys: (pos, tight, sum_so_far). The crucial subtlety: memoize only when tight == 0. When tight == 1, the upper-bound digit at this position depends on N, which is fixed for the run — so technically tight == 1 states are also legitimate to cache. But the canonical idiom is to cache only tight == 0 because (a) those states are reused across the recursion (many paths lead to the same “free” sub-tree), while (b) tight == 1 states are visited at most once per position.

Both forms are correct; the “cache only tight == 0” form is slightly more memory-efficient. Either works for the asymptotic.

4. Pseudocode

DigitDP_DigitSum(N, k):
    digits := decimal digits of N (most significant first), length d
    memo := map from (pos, tight, sum) to count

    function count(pos, tight, sum):
        if pos == d:
            return 1 if sum == k else 0
        if tight == 0 and (pos, tight, sum) in memo:
            return memo[(pos, tight, sum)]

        upper := digits[pos] if tight else 9
        total := 0
        for digit := 0 to upper:
            new_tight := tight and (digit == upper)
            new_sum := sum + digit
            if new_sum > k: continue          # prune
            total += count(pos + 1, new_tight, new_sum)

        if tight == 0:
            memo[(pos, tight, sum)] = total
        return total

    return count(0, tight=1, sum=0)

For range queries [L, R], compute f(R) - f(L - 1) where f(x) = count of valid integers in [0, x]. This converts a range query to two prefix queries via inclusion-exclusion.

5. Python Implementation

from functools import lru_cache
 
def count_in_range_with_digit_sum(N: int, k: int) -> int:
    """Count integers in [0, N] whose digit sum equals k."""
    digits = list(map(int, str(N)))
    d = len(digits)
 
    @lru_cache(maxsize=None)
    def helper(pos: int, tight: int, sum_so_far: int) -> int:
        if pos == d:
            return 1 if sum_so_far == k else 0
        upper = digits[pos] if tight else 9
        total = 0
        for digit in range(upper + 1):
            new_tight = 1 if (tight and digit == upper) else 0
            new_sum = sum_so_far + digit
            if new_sum > k:
                continue
            total += helper(pos + 1, new_tight, new_sum)
        return total
 
    return helper(0, 1, 0)
 
 
# Test
print(count_in_range_with_digit_sum(24, 6))    # 3
print(count_in_range_with_digit_sum(100, 5))   # 6 (5, 14, 23, 32, 41, 50) -> 6
print(count_in_range_with_digit_sum(10**18, 100))   # large, fast

A subtle point: lru_cache keys on the full argument tuple including tight, so it caches both tight == 0 and tight == 1 states. This is fine — the total number of cached states is bounded by d · 2 · (k+1), which is tiny.

5.1 Iterative Tabulation Form

Recursive memoization is the most natural way to write digit DP. An iterative form is possible but uglier:

def count_in_range_with_digit_sum_iter(N: int, k: int) -> int:
    digits = list(map(int, str(N)))
    d = len(digits)
    # dp[pos][tight][sum] for pos in [0, d], tight in {0, 1}, sum in [0, k]
    dp = [[[0] * (k + 1) for _ in range(2)] for _ in range(d + 1)]
    # Base case: pos == d
    for tight in range(2):
        for s in range(k + 1):
            dp[d][tight][s] = 1 if s == k else 0
    # Fill backward
    for pos in range(d - 1, -1, -1):
        for tight in range(2):
            for s in range(k + 1):
                upper = digits[pos] if tight else 9
                total = 0
                for digit in range(upper + 1):
                    new_tight = 1 if (tight and digit == upper) else 0
                    new_sum = s + digit
                    if new_sum > k:
                        continue
                    total += dp[pos + 1][new_tight][new_sum]
                dp[pos][tight][s] = total
    return dp[0][1][0]

Most digit-DP implementations use the recursive form; tabulation offers no speedup and is messier.

5.2 Range [L, R] via Subtraction

def count_in_range(L: int, R: int, k: int) -> int:
    return count_in_range_with_digit_sum(R, k) - count_in_range_with_digit_sum(L - 1, k)

This is the standard idiom: compute “count up to R” and “count up to L-1” and subtract. Works because the property is closed under prefix-counting.

6. Worked Example — Count Numbers Without Substring 49 (Codeforces 55D Variant)

Property: count integers in [0, N] whose decimal representation does not contain the substring 49.

6.1 State Design

  • pos: position (0 to d).
  • tight: 0/1.
  • last_digit: 0..9 plus a “no previous digit” sentinel. To avoid dealing with the sentinel separately, we use last_digit = -1 initially or we reserve 10 as the sentinel.
  • seen_49: boolean (1 if we’ve already placed 49 in the number; 0 otherwise).

We could also drop seen_49 and abort early (return 0) the moment we see 49. Both formulations work.

6.2 Recurrence

count(pos, tight, last_digit):
    if pos == d: return 1
    upper := digits[pos] if tight else 9
    total := 0
    for digit in 0..upper:
        if last_digit == 4 and digit == 9: continue   # would form "49"
        new_tight := tight and (digit == upper)
        total += count(pos + 1, new_tight, digit)
    return total

The last_digit == 4 and digit == 9 check enforces the “no 49” constraint. State size: d × 2 × 10. For d = 19, total ~380 states — extremely small.

6.3 Python

def count_no_49_substring(N: int) -> int:
    digits = list(map(int, str(N)))
    d = len(digits)
 
    @lru_cache(maxsize=None)
    def helper(pos: int, tight: int, last_digit: int) -> int:
        if pos == d:
            return 1
        upper = digits[pos] if tight else 9
        total = 0
        for digit in range(upper + 1):
            if last_digit == 4 and digit == 9:
                continue
            new_tight = 1 if (tight and digit == upper) else 0
            total += helper(pos + 1, new_tight, digit)
        return total
 
    # Use 10 as the "no previous digit" sentinel
    return helper(0, 1, 10)

The pattern is identical to §5; only the auxiliary state and the constraint differ.

7. Variants and Extensions

7.1 Sum of Property Values, Not Just Count

If the question is “sum the property P(x) over all x in [L, R],” the recurrence returns a sum instead of a count. Each leaf returns P(x) for the specific x constructed; internal nodes sum the children. Sometimes you need to track an auxiliary “the sum of remaining-digits is currently s” running variable to compute the final value.

7.2 Digit DP With Leading Zeros

Sometimes the problem distinguishes between numbers with leading zeros (e.g., 5-digit number 00123 = 123) and the actual integer. Add a started flag to the state: started == 0 means we have not placed any non-zero digit yet. This is sometimes needed to exclude the number 0 itself or to count digits correctly.

7.3 Modular Constraints

“Count integers in [L, R] divisible by m whose digit sum is k mod m'”: auxiliary state is (value mod m, digit_sum mod m'). Each state transition multiplies the running value by 10 and adds the new digit, then takes mod. Doable for small m, m' (each adds a multiplicative factor of m to the state size).

7.4 Counting via Combinatorial Pre-computation

For specific properties, you can precompute combinatorial quantities (e.g., binomial coefficients, generating-function values) and combine them at each tight-bound position. This is sometimes faster than the full DP but problem-specific.

7.5 Digit DP Over Bases Other Than 10

Replace 10 with base everywhere. The technique works for binary, hexadecimal, etc. In binary, the per-position branching is 2 instead of 10, often making the DP much smaller. In hexadecimal, it’s 16.

7.6 Multi-Number Digit DP

Some problems ask “count pairs (a, b) with 0 ≤ a, b ≤ N satisfying P”. The state can be enriched to track both numbers’ digits in lockstep. State explodes if both are tight; usually feasible for one or two numbers.

8. Diagram — The Tight-Flag State Machine

flowchart LR
    Start((Start: tight=1)) -- "digit < N[pos]" --> Free((Free: tight=0))
    Start -- "digit == N[pos]" --> Start
    Free -- "any digit 0-9" --> Free
    Start -- "digit > N[pos]" --> Invalid((INVALID: x > N))

    style Invalid fill:#f99

What this diagram shows. A two-state finite automaton describing the tight flag’s evolution as we move position-by-position through the number being constructed. We start in the tight state (the prefix equals N’s prefix). At each position, choosing a digit less than the corresponding digit of N transitions to the free state, where all subsequent digits are unconstrained. Choosing the digit equal to N’s digit keeps us tight. Choosing a greater digit is invalid — it would produce a number exceeding N, so the recursion never explores this branch. The free state is absorbing: once you’re free, you stay free for all remaining positions. This is what lets us safely memoize the DP — once tight = 0, the same (pos, sum) (or whatever auxiliary state) leads to identical sub-problems regardless of which path led here, so caching is valid. Without the tight flag, every path through the recursion would be unique (the bound R couples positions together); with it, the coupling is reduced to a single bit, making the state space polynomial in log R.

9. Common Interview Problems

LC # / SourceProblemState Augmentation
LC 233Count Digit OneCount of digit 1 so far; also closed-form possible
LC 600Non-negative Integers without Consecutive OnesLast digit (binary digit DP)
LC 902Numbers At Most N Given Digit SetAllowed-digit constraint, tight flag
LC 1067Digit Count in RangeSpecific digit count, range subtraction
LC 1397Find All Good StringsAho-Corasick + tight + state
LC 2376Count Special Integers”All digits distinct” → bitmask of used digits + tight
LC 2719Count of IntegersDigit sum range, two tight flags (one per bound)
LC 357Count Numbers with Unique DigitsCombinatorial closed-form, DP also possible
Codeforces 55DBeautiful Numbers (digit-divisibility)LCM mod 2520 + remainder mod 2520 (clever state compression)
AtCoder ABC 154 EAlmost Everywhere ZeroCount of non-zero digits
Codeforces 401DRoman and NumbersBitmask of multi-set + value mod m
Codeforces 628DMagic NumbersPosition parity + digit constraint

The recognition signal: count integers (or sum a function over them) in a huge range [L, R] (typically R ≥ 10^9) where the property depends on digits. If R ≤ 10^7, brute force is fine. Beyond that, digit DP.

10. Pitfalls

10.1 Forgetting to Subtract f(L-1) for Range Queries

Range [L, R] requires f(R) - f(L-1), not f(R) - f(L). Off-by-one if you use f(L) (the value L itself is then excluded).

10.2 Memoizing Across tight = 1 States Incorrectly

If you cache by (pos, sum) only — ignoring tight — you will conflate the constrained and unconstrained sub-problems. The constrained one has fewer choices; the unconstrained one has more. Mixing them up gives the wrong count. Always include tight in the memo key (or only cache tight = 0 and re-execute tight = 1 paths, which is also correct).

10.3 Off-by-One in upper Loop Bound

for digit in range(upper + 1) — inclusive of upper. range(upper) is wrong (skips the upper digit when tight). This is the most common bug in fresh implementations.

10.4 Forgetting Leading-Zero Edge Case

If the problem distinguishes “the number 5” from “the digit string 005” (e.g., counting digits), you need a started flag. Forgetting it counts leading zeros as actual digits and inflates the answer.

10.5 Auxiliary State Too Large

The complexity is dominated by the auxiliary state size. A naive “track the entire digit-sum” state is O(81) for a 9-digit max-sum-81 number — fine. A naive “track all digits placed so far” is O(10^d) — exponential in d, useless. Compress to the minimum sufficient statistic for the property P.

10.6 Mixing 0-Indexed and 1-Indexed Positions

digits[0] is the most significant digit; digits[d-1] is the least. Sometimes the recursion recurses from least-to-most or vice versa. Pick one and document.

10.7 Pruning Too Aggressively

The “if new_sum > k: continue” prune in §3.3 works because the digit sum is monotone. For non-monotone auxiliary states (e.g., value mod m), pruning is unsafe — value mod m can go up and down. Only prune on monotone invariants.

10.8 Forgetting the Base Case Returns 1 (Not Always)

The leaf pos == d typically returns 1 if the property is satisfied at the leaf. But for sum-style queries, it returns the value of the property, not 1. And for “skip leading zeros” queries, you return 1 only if started = 1 (else the number was just 0, possibly excluded). Be precise.

10.9 Confusing tight with loose

Some implementations use loose (the negation of tight) as the flag. Mathematically equivalent, but mixing the two halfway through the implementation produces silently-wrong logic. Pick one and stay consistent.

10.10 Double-Counting When Range Is Inclusive vs Exclusive

If f(x) counts [0, x] inclusive and you want [L, R], use f(R) - f(L-1). If f(x) counts [0, x) exclusive, use f(R+1) - f(L). Off-by-one if you mix conventions.

10.11 lru_cache Key Hashing in Python

For very tight loops (digit DP with S = 10^4 auxiliary states and d = 18), Python’s lru_cache overhead dominates. Switch to manual memoization with a dict keyed on tuples, or — for performance — write in C++. The asymptotic is fine; the constant matters.

11. Variants for Sum of Property

Sometimes you want the sum Σ_{x ∈ [L, R]} P(x) rather than the count |{x : P(x)}|. The recurrence becomes:

sum_dp(pos, tight, ...auxiliary...):
    if pos == d:
        return value at leaf      # the actual value of x as a number, or P(x), etc.
    total := 0
    for digit in 0..upper:
        ...
        total += sum_dp(pos + 1, new_tight, new_aux)
    return total

Computing the value of x requires tracking either (a) the running value mod m (if you want Σ x mod m) or (b) the running value as an integer (if you want Σ x, which requires careful handling at each digit). For “sum of digit sums of all x in [L, R]”, the recurrence accumulates digit sums position-by-position in a clever decomposition.

12. Complexity (Recap)

Time: O(d · 2 · S · base) where:

  • d ≈ log_base(R) is the number of digits in base.
  • 2 is the size of the tight flag.
  • S is the auxiliary state size.
  • base is 10 (decimal) or 2 (binary), the per-position branching.

For typical interview/competitive problems: d ≤ 19, base = 10, S ≤ 10^4. Total: ~10^6 ops — instantaneous.

Space: O(d · 2 · S) for the memo table.

13. Open Questions

  • Is there a clean characterization of “digit-DP-friendly” properties? Properties expressible as a regular language over digits clearly work (the auxiliary state is the DFA’s state). Beyond that, the boundary is fuzzy.
  • Can digit DP be parallelized across position prefixes? The recursion has independent sub-trees once tight is broken, suggesting parallelism, but the constants are usually too small to matter.
  • What’s the relationship between digit DP and automatic sequences in the Cobham-Allouche-Shallit sense? Both involve finite-state recognition of digit-related properties; the connection is real but not commonly leveraged.

A note on the scope of the term. There is no hard line between “digit DP” and “automaton/regular-expression DP” — the latter is simply digit DP whose auxiliary state is the state of a finite automaton over the digit (or character) stream, rather than a numeric quantity like a running digit sum. LeetCode 1397 Find All Good Strings is the canonical example: it counts strings in a lexicographic range [s1, s2] that avoid an “evil” substring, and the standard solution is plainly described as “digit DP” (here over characters) where the auxiliary state is the KMP automaton index tracking how much of evil has been matched (LeetCode 1397 solutions). For multiple forbidden patterns, the automaton is an Aho-Corasick trie and its current node is the auxiliary state. The unifying principle is that any property recognizable by a finite automaton over digits fits the digit-DP frame — the DFA’s state is the minimal sufficient statistic (see §10.5), and the tight flag plus position dimensions are unchanged. The USACO Guide presents digit DP through purely numeric auxiliary states (digit counts, “started” flags) and does not invoke automata explicitly, but this is a narrower exposition, not a different technique. So the earlier hedge here was overcautious: it is entirely standard to call the LC 1397 family digit DP, and this note’s “property on digits” framing already subsumes the automaton case — the automaton state is just one kind of auxiliary state.

14. See Also

Graph View

Backlinks