From the best to the count of all
Every DP you have built in this rung — the interval matrix-chain, the tree DP, the Held-Karp tour — answered an optimization question: find the best arrangement. The state, the transition, and the optimal substructure are all still here, but a counting DP swaps the question for how many arrangements exist at all. The astonishing part is how little changes. Where an optimization transition writes `best[s] = min over choices of (cost + best[next])`, a counting transition writes `ways[s] = sum over choices of ways[next]`. The min or max becomes a plus, and the cost term vanishes because we are tallying, not pricing.
Why is the plus correct? It is the rule-of-sum from counting: if the choices at state s lead to disjoint groups of completions — taking the first item versus skipping it can never produce the same overall arrangement — then the total is the sum of the group sizes. The whole edifice stands or falls on that word disjoint. If two different first choices could finish into the same object, you would double-count, and the sum would be a lie. So a counting DP carries a hidden obligation that an optimization DP does not: you must define the state so that each complete object is generated by exactly one path of choices. Get that wrong and the code runs, returns a number, and overcounts in silence.
Living in a modulus
Counts explode. The number of paths, tilings, or sequences in a problem of size n is routinely exponential in n, far past what a 64-bit integer can hold, so counting problems almost always ask for the answer modulo some prime like 1000000007. This is not a complication bolted on for fun — it is what lets the answer fit in a machine word at all. The good news is that addition and multiplication both commute with the modulus: you may reduce after every `+` and every `*` in the transition, and the final remainder is unchanged. So `ways[s] = (ways[a] + ways[b]) % MOD` keeps every table entry small while preserving the true count's residue.
But be honest about what modular counting throws away. The residue tells you the count mod p, not the count itself: you can no longer say 'is the answer at least one million?' or even 'is it zero?' with full confidence, because a true count that happens to be a multiple of p reduces to 0. You also lose ordinary comparisons — there is no 'bigger' modulo p — so a modular counting DP can never double as an optimization DP. And one subtraction trap waits in counting-by-complement tricks: `(a - b) % MOD` in many languages can go negative, so the safe idiom is `((a - b) % MOD + MOD) % MOD`.
Counting by digit: a state that is a prefix
A beautiful specialty of counting DP is digit DP: count how many integers in a range [L, R] satisfy some property of their decimal digits — say, no two adjacent equal digits, or digit-sum divisible by 7. The naive answer enumerates every number, which is hopeless when R has eighteen digits. Digit DP instead builds numbers one digit at a time, left to right, and counts entire families of completions in one stroke. The trick is a small state that summarizes 'everything later choices need to know about the prefix so far' — and nothing more.
The state usually has three parts: the position you are filling, a 'tight' flag saying whether the prefix so far exactly matches R's prefix (which caps the next digit, since going higher would exceed R), and whatever property accumulator the problem needs (the running digit-sum mod 7, the previous digit, and so on). Counting [L, R] is then done as F(R) - F(L-1), where F(X) counts qualifying numbers in [0, X]. The payoff is dramatic: instead of R+1 numbers you visit on the order of (number of digits) times (a few property states) times (10 digit choices) — polynomial in the digit length, not exponential.
Expectation DP and the gift of linearity
Now point the same table at randomness. An expectation DP asks: if the process makes random moves, what is the expected value of some outcome — the average number of steps, the average score, the chance of eventually winning? The state still summarizes 'where you are', but each entry now holds an expected value, and the transition averages over the random move using its probabilities. If from state s you go to state a with probability p and to state b with probability 1-p, paying one step either way, then `E[s] = 1 + p*E[a] + (1-p)*E[b]`. That weighted sum is the workhorse of the whole subject.
Why may we just average the children's expectations like that? Because of linearity of expectation: E[X + Y] = E[X] + E[Y] for any random variables, even dependent ones. It lets us decompose 'expected total steps' into 'this step (worth 1) plus the expected steps remaining', and the expected remaining steps is itself a weighted average of the children's expectations — which is exactly the transition above. Linearity is the silent partner that makes expectation DP work, the same tool that gave randomized quicksort its O(n log n) expected time back in the randomized-algorithms rung.
There is a real subtlety that does not arise in counting. When the random process can loop back — you might revisit a state before reaching the end — the equations become mutually dependent, like `E[s] = 1 + p*E[s] + (1-p)*E[done]`, where E[s] appears on both sides. That is no longer a simple bottom-up fill: you must solve for E[s] algebraically (here, E[s] = 1/(1-p) + ... after collecting terms), and a tangle of such equations becomes a linear system. Plain tabulation assumes an acyclic dependency DAG; cyclic expectations break that assumption and need either algebra or iterative numerical solving.
One DAG, three readings
Step back and the unity is striking. Optimization, counting, and expectation are the same dependency DAG of subproblems, evaluated in the same topological order; only the operation that combines a state's children differs. Optimization combines with min or max; counting combines with plus (and pays attention to disjointness); expectation combines with a probability-weighted average (and pays attention to cycles). This is why mastering one transfers almost wholesale to the others — the hard work of defining the state and proving the substructure is shared, and only the last algebraic step is swapped.
optimize: f[s] = OPT over choices c of ( value(c) + f[next(s,c)] ) # OPT = min or max count: f[s] = SUM over choices c of ( f[next(s,c)] ) % MOD # choices must be disjoint expectation: f[s] = SUM over choices c of ( prob(c) * f[next(s,c)] ) + local_cost
Two honest closing caveats, because the symmetry can lull you. First, asymptotics still describe scaling, not a verdict at every size: a counting DP and an optimization DP over the same state space share the same Big-O, but the hidden constants differ — modular multiplications are pricier than integer comparisons — so do not read equal Big-O as equal wall-clock. Second, the correctness obligations are genuinely different per flavor: optimization needs optimal substructure, counting needs disjoint choices, expectation needs the cycle structure handled. Borrowing the right transition shape does not let you skip the proof that your state satisfies its flavor's precondition.