---
title: Digit & Probability DP
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 11
order: 811
summary: |
  Two DP patterns with unusual state. _Digit DP_ counts the
  integers in a range $[L, R]$ that satisfy a digit constraint by walking the
  decimal places of the bound, carrying a _tight_ flag that marks when the prefix
  still equals the bound's. _Probability/Expectation DP_ replaces "best value" with
  "expected value," using linearity of expectation to make each state an
  average over its weighted transitions — the natural tool for expected step
  counts and absorbing Markov chains.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming; App. C — Counting & Probability"
  - book: Skiena
    ref: "§ — Dynamic Programming / Combinatorics"
  - book: Erickson
    ref: "Ch. — Dynamic Programming"
practice:
  - title: 'Numbers With Repeated Digits'
    slug: numbers-with-repeated-digits
    difficulty: Hard
  - title: 'Count Numbers with Unique Digits'
    slug: count-numbers-with-unique-digits
    difficulty: Medium
  - title: 'Soup Servings'
    slug: soup-servings
    difficulty: Medium
  - title: 'New 21 Game'
    slug: new-21-game
    difficulty: Medium
---

Most dynamic programs in this section index their subproblems by something you
can point at: a prefix of an array, a remaining capacity, a subset
[encoded as a mask](/algorithms/dynamic-programming/bitmask-dp). Two classic
patterns are harder to see because their state lives in the _structure of a
single object_ — the decimal digits of a number, or the probabilities on the
edges of a process — rather than in an input array. Both still rest on the same
two requirements from the [principles lesson](/algorithms/dynamic-programming/principles):
overlapping subproblems and a substructure that lets us recombine them. What
changes is _what the state must remember_ and _what value it accumulates_.

## Digit DP: counting numbers, not enumerating them

Many problems ask: **how many integers in $[L, R]$ satisfy some property of their
digits?** — no `4` anywhere, digit sum divisible by $7$, no two equal adjacent
digits, at most three distinct digits. The ranges are astronomical ($R$ up to
$10^{18}$), so we cannot loop $x = L \dots R$. But the property depends only on
the digits, and there are at most $19$ of them, so a DP over digit _positions_
runs in time proportional to the number of digits, not their value.

The first move is a standard reduction. Let $f(N)$ count the valid integers in
$[0, N]$. Then the count in $[L, R]$ is $f(R) - f(L - 1)$, so it suffices to
solve the **prefix problem** $f(N)$, counting valid numbers from $0$ up to a
single upper bound $N$.

### Why a plain digit-by-digit count is not enough

Fix $N$ and write it as a digit string $N = d_{m-1} d_{m-2} \cdots d_0$. We build
a candidate number one digit at a time, most-significant first, and at each
position choose a digit. The complication is the **upper bound**. As long as every digit
we have placed so far _equals_ the corresponding digit of $N$, the number is
still pinned to the boundary, so the _next_ digit may range only up to $d_i$ —
go higher and we exceed $N$. But the moment we place a digit strictly _below_
$d_i$, the prefix drops under $N$, and every remaining position is free to use
any digit $0$ through $9$ without risk of overflow.

That single bit of history — _is the prefix still equal to $N$'s prefix?_ — is
exactly the extra state digit DP needs. Call it the **tight** flag.

> **Definition (Tight).** A partially-built prefix is _tight_ if it equals the
> corresponding prefix of the bound $N$ digit-for-digit. While tight, the next
> digit is capped at $d_i$; once any digit is placed below its cap, the prefix
> becomes _free_ and stays free, with all later digits unrestricted in $0\ldots 9$.

$$
% caption: Building a number under the bound $N=325$, most-significant digit
%          first. The single bold path stays tight (each placed digit equals
%          $N$'s digit, so the next digit is capped at $d_i$): cap $d_2=3$, then
%          $d_1=2$, then $d_0=5$, ending at $N$ itself. Any branch placing a
%          digit below the cap turns free ("low" $\le 4$ at the units), after
%          which all later digits range over $0$ to $9$.
\begin{tikzpicture}[
  >=stealth,
  every node/.style={font=\small},
  tnode/.style={circle, draw=acc, very thick, fill=acc!12, minimum size=7mm, inner sep=0},
  fnode/.style={circle, draw, minimum size=7mm, inner sep=0},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % root
  \node[tnode] (r) at (0,3.4) {start};
  % position 0 (hundreds), cap = 3
  \node[fnode] (h0) at (-3.2,1.7) {$0$};
  \node[fnode] (h1) at (-1.6,1.7) {$1$};
  \node[fnode] (h2) at (0,1.7) {$2$};
  \node[tnode] (h3) at (1.7,1.7) {$3$};
  \draw[->] (r) -- node[lbl, above left, pos=.55]{below cap} (h0);
  \draw[->] (r) -- (h1);
  \draw[->] (r) -- (h2);
  \draw[->, acc, very thick] (r) -- node[lbl, right, acc]{cap $d_2$} (h3);
  % free subtree marker under the below-cap children — blue tint, the non-tight category
  \node[lbl, text=acc!70] at (-1.6,0.95) {free: any digit next};
  \draw[acc!70, ->] (-1.6,1.15) -- (-1.6,1.45);
  % position 1 (tens) under the tight node h3, cap = 2
  \node[fnode] (t0) at (0.4,0) {$0$};
  \node[fnode] (t1) at (1.7,0) {$1$};
  \node[tnode] (t2) at (3.0,0) {$2$};
  \draw[->] (h3) -- (t0);
  \draw[->] (h3) -- (t1);
  \draw[->, acc, very thick] (h3) -- node[lbl, right, acc]{cap $d_1$} (t2);
  % position 2 (units) under tight node t2, cap = 5
  \node[tnode] (u5) at (4.3,-1.6) {$5$};
  \node[fnode] (u0) at (2.6,-1.6) {low};
  \draw[->] (t2) -- (u0);
  \draw[->, acc, very thick] (t2) -- node[lbl, right, acc]{cap $d_0$} (u5);
  \node[lbl, acc] at (4.3,-2.4) {equals $N$};
\end{tikzpicture}
$$

The figure shows the crux: there is **exactly one tight path** at any depth — the
one that has matched $N$ digit-for-digit — and it is the only place where the
next digit is capped. Everything hanging off a below-cap choice is _free_, and
free subtrees with the same remaining length and the same carried information are
_identical_, which is precisely the overlapping-subproblem structure that makes
this a DP and not a $10^m$ enumeration.[^clrs-dp]

### The state and recurrence

Beyond position and the tight flag, the state must carry whatever the property
needs to be _checkable incrementally_. For "digit sum $\equiv 0 \pmod 7$" that is
the running sum modulo $7$; for "no `4`" it is nothing extra (we just forbid the
digit `4`); for "no equal adjacent digits" it is the previous digit. Write that
problem-specific carry as $s$.

> **Definition (State).** $\textit{cnt}(i, s, \textit{tight})$ = the number of
> ways to fill digit positions $i, i-1, \dots, 0$ (the remaining, less-significant
> places) so that, combined with the already-placed prefix summarized by carry
> $s$, the completed number is valid _and_ does not exceed $N$, given whether the
> prefix so far is `tight`.

At position $i$ the choosable digits are $d \in \{0, \dots, \text{cap}\}$, where
$\text{cap} = d_i$ when `tight` and $\text{cap} = 9$ when free. Placing $d$
advances to the next position, updates the carry to $s' = \text{step}(s, d)$, and
keeps the prefix tight only if it was tight _and_ $d$ hit the cap:

$$
\textit{cnt}(i, s, \textit{tight})
  \;=\;
  \sum_{d=0}^{\text{cap}}
  \textit{cnt}\parens{i - 1,\; \text{step}(s, d),\; \textit{tight} \wedge [\,d = d_i\,]}.
$$

The base case is reaching past the last position, $i = -1$: return $1$ if the
accumulated carry $s$ marks a valid number (e.g. $s \equiv 0$ for the divisibility
property) and $0$ otherwise. The answer is $\textit{cnt}(m-1, s_0, \textbf{true})$,
starting tight at the most-significant digit.

> **Lemma (optimal/total substructure).** The count of valid completions of a
> prefix depends on the prefix _only_ through $(i, s, \textit{tight})$.

> **Proof.** Two prefixes that agree on remaining length $i+1$, on the carry $s$,
> and on whether they are tight admit exactly the same set of legal digit
> continuations: the per-digit validity test reads only $s$, and the upper-bound
> cap reads only `tight` (and, when tight, the fixed digit $d_i$ of $N$). Hence
> the number of valid completions is a function of $(i, s, \textit{tight})$ alone,
> so distinct prefixes sharing that triple are interchangeable and the
> subproblem is well-defined and reusable. $\qed$

$$
% caption: Why memoization collapses the tree, for the bound $N=325$. The single blue
%          column is the tight boundary path (positions $2,1,0$): visited exactly once and
%          never cached, since it depends on $N$'s own digits. Every below-cap choice drops
%          into the free region, where states are keyed only by $(\text{position},\,s)$ and
%          are shared (memoized) across all the prefixes that reach them — the boxed
%          free-state at each position stands for one cached entry reused by many branches
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % tight column on the left
  \node[circle, draw=acc, very thick, fill=acc!14, minimum size=8mm, inner sep=0] (p2) at (0,0) {pos 2};
  \node[circle, draw=acc, very thick, fill=acc!14, minimum size=8mm, inner sep=0] (p1) at (0,-1.6) {pos 1};
  \node[circle, draw=acc, very thick, fill=acc!14, minimum size=8mm, inner sep=0] (p0) at (0,-3.2) {pos 0};
  \draw[->, acc, very thick] (p2) -- node[right, text=acc]{cap} (p1);
  \draw[->, acc, very thick] (p1) -- node[right, text=acc]{cap} (p0);
  \node[text=acc] at (0,0.85) {\texttt{tight} path};
  % free region boxes on the right, one cached entry per position
  \node[draw, minimum width=22mm, minimum height=7mm, inner sep=2pt] (f2) at (4.0,0) {free at pos 2};
  \node[draw, minimum width=22mm, minimum height=7mm, inner sep=2pt] (f1) at (4.0,-1.6) {free at pos 1};
  \node[draw, minimum width=22mm, minimum height=7mm, inner sep=2pt] (f0) at (4.0,-3.2) {free at pos 0};
  \node at (4.0,0.85) {memoized};
  % below-cap branch dots that all reuse the same free entry (fan-in)
  \node[circle, fill=black!45, inner sep=1.4pt] (b1) at (1.7,0.5) {};
  \node[circle, fill=black!45, inner sep=1.4pt] (b2) at (1.7,0) {};
  \node[circle, fill=black!45, inner sep=1.4pt] (b3) at (1.7,-0.5) {};
  \node[font=\footnotesize, align=center] at (1.7,-1.0) {\texttt{below-cap}\\\texttt{branches}};
  \draw[->] (b1) -- (f2);
  \draw[->] (b2) -- (f2);
  \draw[->] (b3) -- (f2);
  \draw[->] (p2) -- (f2);
  % free states cascade to the next position
  \draw[->] (f2) -- (f1);
  \draw[->] (f1) -- (f0);
  \draw[->] (p1) -- (f1);
  \draw[->] (p0) -- (f0);
\end{tikzpicture}
$$

This is why the carry $s$ must be chosen to be _exactly_ the information the
validity test consumes — no more (or the state space blows up) and no less (or
the substructure breaks). Memoizing on $(i, s, \textit{tight})$ collapses the
exponential tree to a table.[^erickson-dp]

```algorithm
caption: $\textsc{DigitCount}(N)$ — count valid integers in $[0, N]$, memoized
number: 1
$D \gets$ decimal digits of $N$, most-significant first, length $m$
$\textit{memo} \gets$ empty map  // keyed by $(i, s)$, free case only
$\textbf{function } \textsc{Rec}(i, s, \textit{tight})$:
  if $i = -1$ then $\textbf{return } [\,s \text{ is accepting}\,]$  // 1 or 0
  if not $\textit{tight}$ and $(i, s) \in \textit{memo}$ then return $\textit{memo}[i, s]$
  $\text{cap} \gets D[i]$ if $\textit{tight}$ else $9$
  $\textit{total} \gets 0$
  for $d \gets 0$ to $\text{cap}$ do
    if $d$ is forbidden given $s$ then continue   // property-specific prune
    $\textit{total} \gets \textit{total} + \textsc{Rec}\parens{i-1,\ \textsc{Step}(s,d),\ \textit{tight} \text{ and } d = D[i]}$
  if not $\textit{tight}$ then $\textit{memo}[i, s] \gets \textit{total}$
  $\textbf{return } \textit{total}$
$\textbf{return } \textsc{Rec}(m-1,\ s_0,\ \textbf{true})$
```

To ground the recurrence, count the integers in $[0, 325]$ that contain **no digit
`4`**. Here the carry $s$ is empty — validity depends only on forbidding the digit
`4` — so a free state is keyed by position alone. Let $g(i)$ be the number of valid
ways to fill $i$ remaining free positions: each place picks any of the $9$ non-`4`
digits, so $g(i) = 9^i$, giving $g(0)=1$, $g(1)=9$, $g(2)=81$. Now walk the tight
path of $N = 325$, and at each position sum the free completions of the below-cap
digits:

- **Hundreds** (cap $3$): a leading digit in $\{0, 1, 2\}$ is below the cap and
  none is `4`, so each opens $g(2) = 81$ free completions: $3 \times 81 = 243$.
  Digit `3` keeps the prefix tight and continues down.
- **Tens** (cap $2$, prefix `3`): below-cap digits $\{0, 1\}$ are valid, each with
  $g(1) = 9$ completions: $2 \times 9 = 18$. Digit `2` stays tight.
- **Units** (cap $5$, prefix `32`): below-cap digits $\{0, 1, 2, 3\}$ are valid
  (excluding `4`, which is below the cap but forbidden), contributing $4 \times
  g(0) = 4$. Digit `5` completes the tight path at $N = 325$ itself, which contains
  no `4`, so it counts as $1$.

Summing the tight path: $243 + 18 + 4 + 1 = 266$, matching a brute-force count over
all $326$ integers. The DP touched three positions instead of enumerating them.

Note the memo caches **only the free states**: tight states lie on the single
boundary path, are visited once, and depend on $N$'s specific digits, so caching
them would be both useless and unsound across different bounds. With $m \le 19$
positions, a carry $s$ from a small set $S$, and $10$ digit choices, the running
time is $O(m \cdot |S| \cdot 10)$ — for "no `4`" that is a few hundred operations
to count over $[0, 10^{18}]$. **Count Numbers with Unique Digits** and **Numbers
With Repeated Digits** are this template with $s$ tracking a $10$-bit mask of used
digits; the latter is cleanest as $R - (\text{count with all-distinct digits})$.[^skiena-dp]

::impl{algo="digit_dp"}

## Probability & Expectation DP: averaging instead of optimizing

The second pattern keeps the DP skeleton but changes the operator. An
optimization DP combines child values with $\min$ or $\max$; a **probability DP**
combines them with a _probability-weighted sum_. The value stored in a state is
no longer "the best you can do from here" but "the **expected** value of the
random process started from here." The key fact is **linearity of expectation**:
the expected value of a state is the average of its successors' expected values,
each weighted by the transition probability — and this holds whether or not the
transitions are independent.

The classic instance is the **expected number of steps to absorption** in a
random walk. Consider a process that moves between states by chance and eventually
reaches a terminal (_absorbing_) state. We want the expected number of steps from
each starting state.

$$
% caption: A small absorbing process. From state $A$, with probability
%          $\tfrac12$ we step to $B$ and with probability $\tfrac12$ to the
%          absorbing $\text{End}$; from $B$ we go to $A$ or to $\text{End}$,
%          each with probability $\tfrac12$ (every edge is labelled "half").
%          $E[\cdot]$ is the expected steps to reach End, and solving the system
%          gives $E[A]=\tfrac{8}{3}$, $E[B]=\tfrac{7}{3}$, $E[\text{End}]=0$.
\begin{tikzpicture}[
  >=stealth,
  every node/.style={font=\small},
  st/.style={circle, draw, minimum size=10mm, inner sep=1pt},
  abs/.style={circle, draw=green, very thick, fill=green!12, minimum size=10mm, inner sep=1pt},
  plbl/.style={font=\footnotesize, acc}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[st] (A) at (0,0) {$A$};
  \node[st] (B) at (3.2,0) {$B$};
  \node[abs] (E) at (6.4,0) {End};
  % A -> B and B -> A (curved, two directions)
  \draw[->, acc] (A) to[out=35,in=145] node[plbl, above]{half} (B);
  \draw[->, acc] (B) to[out=215,in=325] node[plbl, below]{half} (A);
  % A -> End (long arc over the top)
  \draw[->, acc] (A) to[out=70,in=110] node[plbl, above]{half} (E);
  % B -> End
  \draw[->, acc] (B) to[out=35,in=145] node[plbl, above]{half} (E);
  % expected-value annotations under nodes
  \node[font=\footnotesize, acc] at (0,-1.1) {$E[A]$};
  \node[font=\footnotesize, acc] at (3.2,-1.1) {$E[B]$};
  \node[font=\footnotesize, green] at (6.4,-1.1) {$E=0$};
\end{tikzpicture}
$$

> **Definition (State).** $E[v]$ = the expected number of steps for the process to
> reach an absorbing state, starting from state $v$. For an absorbing state,
> $E[v] = 0$.

Each step costs $1$, and after that step we are in a successor $u$ chosen with
probability $p(v, u)$, from which the remaining expected cost is $E[u]$. Linearity
of expectation turns this into one equation per state:

$$
E[v] \;=\; 1 + \sum_{u} p(v, u)\, E[u],
\qquad E[\text{absorbing}] = 0.
$$

The "$1$" is the step just taken; the sum is the expected remaining cost,
averaged over where that step lands.[^clrs-prob] For the figure, $E[A] = 1 + \tfrac12 E[B] +
\tfrac12 \cdot 0$ and $E[B] = 1 + \tfrac12 E[A] + \tfrac12 \cdot 0$; solving the
two-by-two system gives $E[A] = 8/3$ and $E[B] = 7/3$.

### When is this a DP, and when a linear system?

The recurrence above is a genuine DP — solvable by memoization or a bottom-up
sweep — **exactly when the dependency graph on states is acyclic**, so that each
$E[v]$ depends only on states already computed. That is the common, easy case:
games that strictly advance (a counter that only grows, a round number that only
increases, soup that only gets consumed), where you evaluate states in reverse
topological order and read off the answer.

> **Note.** When the transitions form _cycles_ — like $A \leftrightarrow B$ above,
> where $E[A]$ depends on $E[B]$ and vice versa — there is no topological order, so
> the equations cannot be unrolled by plain DP. They still form a linear system
> $E = \mathbf{1} + P E$ in the unknown expectations, solvable by Gaussian
> elimination. Treat acyclicity as the dividing line: acyclic means DP, cyclic
> means solve the system.

The same $E[v] = 1 + \sum p(v,u) E[u]$ shape computes **expected values** other
than step counts — replace the constant $1$ by the per-step reward, or drop it
and let an accepting state contribute its payoff — and **hitting probabilities**,
where $P[v] = \sum_u p(v,u) P[u]$ with boundary states pinned to $0$ or $1$. The
acyclic, DP-friendly versions are the staple of competitive problems.

> **Intuition.** An optimization DP takes a $\min$/$\max$ over children. An
> expectation DP has no choice to make — the child is selected by chance — so it
> takes a probability-weighted sum. The state,
> the substructure, and the memo table are identical; only the combining operator
> changes.

### A worked acyclic example: expected die rolls to a target

Roll a fair $6$-sided die repeatedly, summing the pips, and stop the instant the
running total is $\ge T$. What is the expected number of rolls? Let $E[t]$ be the
expected additional rolls when the current total is $t < T$ (and $E[t] = 0$ for
$t \ge T$). One roll lands on $1, \dots, 6$ each with probability $\tfrac16$:

$$
E[t] \;=\; 1 + \frac{1}{6}\sum_{k=1}^{6} E[t + k],
\qquad E[t \ge T] = 0.
$$

Because every transition strictly _increases_ $t$, the dependency graph is acyclic
and we fill $E$ from $t = T-1$ downward — a textbook one-dimensional DP. **Soup
Servings** is the same shape in two dimensions (the two soup volumes only
decrease, so the state space is acyclic and finite), and **New 21 Game** is a
probability-DP over a sliding window of point totals, made $O(n)$ by maintaining a
running sum of the window of $E$-values rather than re-summing each transition.

$$
% caption: The acyclic dependency graph for expected die rolls with target $T$. Each total
%          $t$ depends only on the larger totals $t+1,\dots,t+6$ (one die step), so every
%          edge points rightward and the graph has no cycle. Totals $\ge T$ are absorbing
%          with $E=0$ (green); evaluating right-to-left (reverse topological order) finalizes
%          each $E[t]$ from values already known. Blue arrows show the six transitions out of
%          one state
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % live states (non-absorbing)
  \foreach \x/\lab in {0/{T-2},1/{T-1}} {
    \node[circle, draw, minimum size=9mm, inner sep=1pt] (n\x) at ({\x*2.4},0) {\texttt{\lab}};
  }
  % absorbing states (green)
  \foreach \x/\lab in {2/{T},3/{T+1}} {
    \node[circle, draw=green, very thick, fill=green!12, minimum size=9mm, inner sep=1pt, text=green] (n\x) at ({\x*2.4},0) {\texttt{\lab}};
  }
  % dependency edges (rightward only)
  \draw[->, acc, thick] (n0) to[bend left=22] node[above, font=\scriptsize, text=acc]{step} (n1);
  \draw[->, acc, thick] (n0) to[bend right=42] node[midway, below, font=\scriptsize, text=acc]{step} (n2);
  \draw[->, acc, thick] (n1) -- (n2);
  \draw[->, acc, thick] (n1) to[bend left=42] (n3);
  % evaluation-order annotation (avoid fi/fl ligature words)
  \draw[->, thick] (8.2,-2.0) -- (-0.6,-2.0) node[midway, below, font=\scriptsize]{evaluate larger totals earlier};
  \node[text=green, font=\scriptsize] at (6.0,1.55) {absorbing E equals 0};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{ExpectedRolls}(T)$ — expected fair-die rolls to reach total $\ge T$
number: 2
$E[t] \gets 0$ for all $t \ge T$
for $t \gets T - 1$ down to $0$ do
  $s \gets 0$
  for $k \gets 1$ to $6$ do
    $s \gets s + E[t + k]$       // each outcome with prob $1/6$
  $E[t] \gets 1 + s / 6$         // the $1$ counts this roll
$\textbf{return } E[0]$
```

The reverse-topological sweep is what makes this $O(T)$ and not a linear-system
solve: each $E[t]$ reads only larger totals, already finalized. The window sum
trick (subtract the leaving term, add the entering one) drops the inner loop and
yields $O(T)$ even when the die has many faces — the same optimization that turns
**New 21 Game** from $O(nk)$ into $O(n)$.

::impl{algo="expected_die_rolls,absorbing_markov_chain"}

## What these two patterns really are

Digit DP is a special case of a much older idea: counting the accepting paths of a
**finite automaton** over a bounded input. The digit-by-digit walk traces a run
of a deterministic automaton whose states are the carries $s$, and the "count valid
numbers $\le N$" question is the **automaton-intersection count** between that
property-automaton and the "less-than-or-equal-to-$N$" automaton — the tight flag is
the state of the second automaton. Once framed this way, digit DP
generalizes far past base $10$: the same technique counts binary strings avoiding a
pattern (a transfer-matrix / regular-language count), lattice points under algebraic
constraints, and, in the theory of **automatic sequences** (Allouche and Shallit,
_Automatic Sequences_, 2003), whole families of number-theoretic counting functions.
For a fixed carry-automaton the count is a **transfer-matrix** product, so $f(N)$ can
even be computed by matrix exponentiation in $O(|S|^3 \log N)$ when the number of
positions is huge.[^dp-beyond]

Expectation DP is standard **Markov chain theory**. The system
$E = \mathbf{1} + P E$ is the standard **expected hitting time** to an absorbing set,
and the matrix that makes it solvable is the **fundamental matrix**
$N = (I - Q)^{-1}$ of the transient part $Q$, whose row sums give the expected
steps to absorption (Kemeny and Snell, _Finite Markov Chains_, 1960). The acyclic
"DP" case is precisely when $Q$ is nilpotent (can be permuted to strictly triangular
form), so the inverse is a finite sum and no linear solve is needed — the reverse
topological sweep is Gaussian elimination that happens to require no back-substitution.
This is the same object behind **absorbing random walks** on graphs, the **gambler's
ruin** problem, and the stationary analysis that underlies Google's original
PageRank (Page, Brin, Motwani, Winograd, 1999), where the relevant quantity is the
stationary distribution of a chain rather than a hitting time, but the linear-algebra
machinery is identical. The dividing line this lesson draws — acyclic means DP, cyclic
means solve the system — is the boundary between a nilpotent and a general transient
matrix.

## Takeaways

- **Digit DP** counts integers in $[L, R]$ with a digit property by solving the
  prefix problem $f(N)$ and using $f(R) - f(L-1)$; it walks the $\le 19$ decimal
  positions of the bound rather than the $10^{18}$ values.
- The essential extra state is the **tight** flag: while the built prefix equals
  $N$'s prefix the next digit is capped at $d_i$; the first below-cap digit makes
  it _free_, after which all later digits range over $0$–$9$. State is
  $(\textit{position}, \textit{carry } s, \textit{tight})$, and only **free**
  states are memoized.
- Choose the carry $s$ to be _exactly_ what the validity test reads (running sum
  mod $k$, previous digit, used-digit mask) — no more, no less — so the
  substructure holds and the table stays small.
- **Expectation DP** stores $E[v]$ = expected value from state $v$ and combines
  children with a **probability-weighted sum**, $E[v] = 1 + \sum_u p(v,u) E[u]$,
  by linearity of expectation; absorbing states have $E = 0$.
- It is a plain **DP when the state graph is acyclic** (quantities that only
  advance) — evaluate in reverse topological order — and a **linear system** when
  transitions form cycles, solved by Gaussian elimination instead.

[^clrs-dp]: **CLRS**, Ch. 15 — Dynamic Programming: overlapping subproblems and optimal substructure, the two conditions that let digit and expectation DPs reuse subproblem solutions across a position/carry state.
[^clrs-prob]: **CLRS**, App. C — Counting & Probability (C.3, indicator random variables): linearity of expectation holds without independence, which is what licenses $E[v] = 1 + \sum_u p(v,u)E[u]$ as a per-state recurrence.
[^erickson-dp]: **Erickson**, Ch. — Dynamic Programming: the discipline of identifying the _minimal_ summary a subproblem must carry — here the tight flag plus a problem-specific digit carry, or the expected-value scalar per state.
[^skiena-dp]: **Skiena**, § — Dynamic Programming / Combinatorics: counting DPs that accumulate a sum over choices rather than a min/max, with bounded-range digit counting as a recurring instance.
[^dp-beyond]: **Allouche & Shallit**, _Automatic Sequences_ (2003) for the finite-automaton / transfer-matrix view of digit counting; **Kemeny & Snell**, _Finite Markov Chains_ (1960) for the fundamental matrix $(I-Q)^{-1}$ giving expected steps to absorption, of which the acyclic expectation DP is the nilpotent-$Q$ special case.